Python merge sort problem

Question

I don't know where I am mistaken in my implementation of merge sort in python.

import sys sequence = [6, 5, 4, 3, 2, 1] def merge_sort(A, first, last): if first < last: middle = (first + last) / 2 merge_sort(A, first, middle) merge_sort(A, middle+1, last) merge(A, first, middle, last) def merge(A, first, middle, last): L = A[first:middle] R = A[middle:last] L.append(sys.maxint) R.append(sys.maxint) i = 0 j = 0 for k in xrange(first, last): if L[i] <= R[j]: A[k] = L[i] i = i + 1 else: A[k] = R[j] j = j + 1 merge_sort(sequence, 0, len(sequence)) print sequence 

I would really appreciate it if anyone could point out what is violating my current merge sort implementation.

Answer 1

The problem is here:

  merge_sort(A, first, middle) merge_sort(A, middle+1, last) # BEEP 

You only sort the second part from the middle + 1, when you should start in the middle. In fact, you never reorder an element in the middle.

Of course you cannot write

  merge_sort(A, first, middle) merge_sort(A, middle, last) # BEEP, BEEP 

because when last = first + 1, you first get the middle == and plunge into infinite recursion (stops at RuntimeError: maximum recursion depth exceeded )

So the way:

  merge_sort(A, first, middle) if middle > first: merge_sort(A, middle, last) 

After this small change, your implementation produces the correct results.

Answer 2

There are 2 errors in the code:

• if first < last: should be if first < last and last-first >= 2:
• merge_sort(A, middle+1, last) should be merge_sort(A, middle, last)