Merge sort implementation in Python

Question

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

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

Answer 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.

• MattTheSnake: 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.