def mergesort( array ):
# array is a list
#base casee
if len(array) <= 1:
return array
else:
split = int(len(array)/2)
#left and right will be sorted arrays
left = mergesort(array[:split])
right = mergesort(array[split:])
sortedArray = [0]*len(array)
#sorted array "pointers"
l = 0
r = 0
#merge routine
for i in range(len(array)):
try:
#Fails if l or r excede the length of the array
if left[l] < right[r]:
sortedArray[i] = left[l]
l = l+1
else:
sortedArray[i] = right[r]
r = r+1
except:
if r < len(right):
#sortedArray[i] = right[r]
#r = r+1
for j in range(len(array) - r-l):
sortedArray[i+j] = right[r+j]
break
else:
#sortedArray[i] = left[l]
#l = l+1
for j in range( len(array) - r-l):
sortedArray[i+j] = left[l+j]
break
return sortedArray
\$\begingroup\$
\$\endgroup\$
2
-
\$\begingroup\$ I'm confused, I thought a merge sort would always take 2 lists as input and return one list as output. \$\endgroup\$pacmaninbw– pacmaninbw ♦2016-09-13 17:21:40 +00:00Commented Sep 13, 2016 at 17:21
-
\$\begingroup\$ @pacmaninbw I don't believe so. Merge sort is an algorithm for taking an unsorted list and turning it into a sorted list. There is a main section of merge sort called the merge where two sorted lists are combined into one sorted list. In my code the two sorted lists are "left" and "right" \$\endgroup\$MattTheSnake– MattTheSnake2016-09-13 18:59:20 +00:00Commented Sep 13, 2016 at 18:59
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
1
First of all, the code suffers a very typical problem. The single most important feature of merge sort is stability: it preserves the order of the items which compare equal. As coded,
if left[l] < right[r]:
sortedArray[i] = left[l]
l = l+1
else:
sortedArray[i] = right[r]
r = r+1
of two equals the right one is merged first, and the stability is lost. The fix is simple:
if left[l] <= right[r]:
(or if right[i] < left[i]: if you prefer).
I don't think that try/except on each iteration is a way to go. Consider
try:
while i in range(len(array)):
....
except:
....
Of course here i is not known in the except clause. Again, the fix is simple. Notice that the loop is never terminated by condition: either left or right is exhausted before i reaches limit. It means that testing the condition is pointless, and i is an index on the same rights as l and r:
l = 0
r = 0
i = 0
try:
while True:
....
except:
....
Naked except are to be avoided. Do except IndexError: explicitly.
-
\$\begingroup\$ Thanks for the suggestions! I tested out the changes you suggested and I got about a 0.3s improvement on an original 7.1s time for sorting a list of of 1 million random integers. I understand the second suggestion but I don't get the first one. Is the first suggestion important when its not just integers your sorting? I was able to use this suggestion to make my inversion counting algorithm more robust. \$\endgroup\$MattTheSnake– MattTheSnake2016-09-14 14:07:28 +00:00Commented Sep 14, 2016 at 14:07