Mergesort through recursion

Question

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)

Answer 1

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
    while read_left < len(temp) and read_right < hi:
        if alist[read_right] < temp[read_left]:
            alist[write] = alist[read_right]
            read_right += 1
        else:
            alist[write] = temp[read_left]
            read_left += 1
        write += 1
    # Copy any unprocessed items in temp back to alist
    alist[write:write+len(temp)-read_left] = temp[read_left:]
    # Any unprocessed items in right subarray are already in place!
    # Nothing returned: the list gets sorted in-place

Answer 2

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.