# Mergesort through recursion

Could someone kindly have a look at the recursive merge sort below and let me know if there are any improvements? I'm mainly interested in either improving the code speed or making the code shorter.

def mergesort(alist):
if len(alist) > 1:
mid = len(alist)/2
left = alist[:mid]
right = alist[mid:]

mergesort(left)
mergesort(right)

i = 0
j = 0
k = 0

while i < len(left) and j < len(right):
if left[i] > right[j]:
alist[k] = right[j]
j = j + 1

elif left[i] < right[j]:
alist[k] = left[i]
i = i + 1

k = k + 1

while i < len(left):
alist[k] = left[i]
i = i + 1
k = k + 1

while j < len(right):
alist[k] = right[j]
j = j + 1
k = k + 1

A = [4, 3, 1, 2, 6, 8, 10]

mergesort(A)
print(A)


Slicing a list makes a copy of it, e.g.:

>>> a = list(range(10))
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> b = a[:5]
>>> b
[0, 1, 2, 3, 4]
>>> b[2] = 0
>>> b
[0, 1, 0, 3, 4]
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


So each of your recursive calls is creating a copy of half of the list before passing it down, which is not the best use of time. I think it is a much better approach to pass around the whole list, which simply passes a reference to it around, no copies involved, and a couple of indices marking the range you want to work on:

def mergesort(alist, lo=0, hi=None):
if hi is None:
hi = len(alist)
if hi - lo <= 1:
return
mid = lo + (hi - lo) // 2  # mid = (lo + hi) // 2 can overflow
mergesort(alist, lo=lo, hi=mid)
mergesort(alist, lo=mid, hi=hi)
# Copy out the left side, which may be overwritten by the merge
temp = alist[lo:mid]
read_left = 0  # index into temp, copy of left subarray
read_right = mid  # index into alist's right subarray
write = lo  # index into alist
else:
write += 1
# Copy any unprocessed items in temp back to alist
# Any unprocessed items in right subarray are already in place!
# Nothing returned: the list gets sorted in-place


Why not change

while i < len(left) and j < len(right):
if left[i] > right[j]:
alist[k] = right[j]
j = j + 1

elif left[i] < right[j]:
alist[k] = left[i]
i = i + 1

k = k + 1


to

while i < len(left) and j < len(right):
if left[i] > right[j]:
alist[k] = right[j]
j = j + 1

else:  // !! Note the 'else'
alist[k] = left[i]
i = i + 1

k = k + 1


That way you do not "skip" (possible) equal elements.

Edit: Even worse, if you add any duplicate element into the input array, your implementation will loop forever.