CODEWITHSUNDEEP
pythonrecursionmergesort
Derek Xie
Derek Xie

Reputation: 111

The use of recursion in merge sort for python

I am learning merge sort in python, and I am a little confused by the implementation of the following program. According to my understanding, when mergeSort ([3,1], compare) is implemented, it splits into mergeSort([3], compare) and mergeSort([1], compare). and then merge([3],[1], compare) should be called, so that the print statement should be left = [1,3], but the program actually prints out left = [3,1], same for other print statements, why? Thank you very much.

def merge(left, right, compare):
    """Assumes left and right are sorted lists and compare defines an ordering
       on the elements.
       Returns a new sorted (by compare list containing the same elements as
       (left + right) would contain."""
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while (i < len(left)):
        result.append(left[i])
        i += 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result

import operator

def mergeSort(L, compare = operator.lt):
    """Assumes L is a list, compare defines an ordering on elements of L
       Returns a new sorted list containing the same elements as L"""
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        print "middle =", middle
        left = mergeSort(L[:middle], compare)
        print "left = ", L[:middle]
        right = mergeSort(L[middle:], compare)
        print "right = ", L[middle:]
        return merge(left, right, compare)

>>> L = [3,1,2,5,4,9,6,7,8]
>>> mergeSort(L, compare = operator.lt)
middle = 4
middle = 2
middle = 1
left =  [3]
right =  [1]
left =  [3, 1]
middle = 1
left =  [2]
right =  [5]
right =  [2, 5]
left =  [3, 1, 2, 5]
middle = 2
middle = 1
left =  [4]
right =  [9]
left =  [4, 9]
middle = 1
left =  [6]
middle = 1
left =  [7]
right =  [8]
right =  [7, 8]
right =  [6, 7, 8]
right =  [4, 9, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Upvotes: 2

Views: 198

Answers (3)

Trevor Merrifield
Trevor Merrifield

Reputation: 4691

This code prints L as it is being recursively split apart. It doesn't actually print the result of any merges. You can see the result of each merge by changing the line

return merge(left, right, compare)

to

merged = merge(left, right, compare)
print "merged = ", merged
return merged

Upvotes: 0

user4754843
user4754843

Reputation: 

left = mergeSort(L[:middle], compare)
print "left = ", left
right = mergeSort(L[middle:], compare)
print "right = ", right

This should work.

Upvotes: 1

Julien
Julien

Reputation: 15071

This is the problem:

    print "left = ", L[:middle] # content of L before sorting

Replace this line and other analogous print statements with:

    print "left = ", left # actual result of mergeSort

Upvotes: 2

Related Questions