# 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. Sep 13, 2016 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" Sep 13, 2016 at 18:59

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. Sep 14, 2016 at 14:07