CODEWITHSUNDEEP
pythonsortingrecursionmerge
TripleH
TripleH

Reputation: 479

a bug of merge sort using Python

I am working on merge sort using recursive Python. I couldn't find out where I made mistake and always got wrong answers. The code is as follows:

def mergeSort(xlist):
    print ('Splitting',xlist, len(xlist))
    if len(xlist)>1:
       midpoint = len(xlist) // 2
       left  = xlist[:midpoint]
       right = xlist[midpoint:]
       print ('----------------------------')
       mergeSort(left)
       mergeSort(right)

       print (left, 'r', right)

       while len(right) >0:
          left.append(right[0])
          right.remove(right[0])
          slot= len(left)-1
          while slot >0:
              if left[slot] < left[slot-1]: left[slot], left[slot-1] = left[slot-1], left[slot]
              slot -= 1

       print ('sorted',left, right,xlist)
       return left

print('A',mergeSort([100,1,91,54]))

When merging, the output also shows in the wrong way, like:

 Splitting [100, 1, 91, 54] 
 ---------------------------- 
 Splitting [100, 1] 2
 ---------------------------- 
 Splitting [100] 1 
 Splitting [1] 1 
 [100] r [1] 
 sorted [1, 100] [] [100, 1]
 Splitting [91, 54] 2
 ---------------------------- 
 Splitting [91] 1 
 Splitting [54] 1 
 [91] r [54] 
 sorted [54, 91] [] [91, 54]
 [100, 1] r [91, 54] 
 sorted [1, 54, 100, 91] [] [100, 1, 91, 54]
 A [1, 54, 100, 91]

I expect the last third line should be "[1,100] r [54, 91]" after return back. What is wrong here? I know there is a code in interactivePython.org, but I wish to understand where I made logical mistake. Can anyone help me? A ton of thanks!

Upvotes: 1

Views: 122

Answers (2)

Prune
Prune

Reputation: 77837

It took me a few minutes, but I found it. You recur on the left & right halves properly, but then you throw away the results and merge the original lists. Correction:

    print ('----------------------------')
    left  = mergeSort(left)
    right = mergeSort(right)

I expect you can see the effect now.

Here's the working code that produced the output above:

def mergeSort(xlist):
    print 'Splitting', xlist, len(xlist)
    if len(xlist) <= 1:
        return xlist
    else:
        midpoint = len(xlist) // 2
        left  = xlist[:midpoint]
        right = xlist[midpoint:]
        print ('----------------------------')
        left  = mergeSort(left)
        right = mergeSort(right)

        print left, 'r', right

        # print "merge", left, right
        while len(right) > 0:
            left.append(right[0])
            right.remove(right[0])
            slot = len(left) - 1
            while slot > 0:
                if left[slot] < left[slot-1]:
                    left[slot], left[slot-1] = left[slot-1], left[slot]
                # print "switched", left
                slot -= 1

        print 'sorted', left, right, xlist
        return left

print 'A',mergeSort([100,1,91,54])

Output:

A Splitting [100, 1, 91, 54] 4
----------------------------
Splitting [100, 1] 2
----------------------------
Splitting [100] 1
Splitting [1] 1
[100] r [1]
sorted [1, 100] [] [100, 1]
Splitting [91, 54] 2
----------------------------
Splitting [91] 1
Splitting [54] 1
[91] r [54]
sorted [54, 91] [] [91, 54]
[1, 100] r [54, 91]
sorted [1, 54, 91, 100] [] [100, 1, 91, 54]
[1, 54, 91, 100]

Upvotes: 0

Blckknght
Blckknght

Reputation: 104712

You need to decide whether your mergesort code is going to modify the list it is passed in place, or if it is going to return a new list. The top part of your code is written as if it will modify the list in place. The bottom half is written as if it returns a new list. They both need to work the same way, or the sort won't work.

If you want to stick with the modify-in-place approach, the top part of the code is fine, it's just the merging of left and right at the end that you need to fix up. Instead of merging into left, you need to merge into xlist. I'd suggest using separate indexes into each of the three lists, rather than doing costly insertions into left like you're currently doing.

If you want to return a new list, you need to change the top part of the code. If you hit the base case (len(xlist) < 2), you need to return xlist unmodified. You also need to save the return values from the recursive calls, perhaps with left = mergesort(left) and right = mergesort(right). Your later merging code is probably OK, though it discards most of the performance advantages of merge sort, since the insertion logic is O(N**2).

Upvotes: 1

Related Questions