# Merge sort implementation in Python

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  = *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

• I'm confused, I thought a merge sort would always take 2 lists as input and return one list as output. – pacmaninbw Sep 13 '16 at 17:21
• @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" – MattTheSnake Sep 13 '16 at 18:59

## 1 Answer

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.

• 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. – MattTheSnake Sep 14 '16 at 14:07