The use of recursion in merge sort for python
<p>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 <code>mergeSort ([3,1], compare)</code> is implemented, it splits into <code>mergeSort([3], compare)</code> and <code>mergeSort([1], compare)</code>. and then <code>merge([3],[1], compare)</code> should be called, so that the <code>print</code> statement should be <code>left = [1,3]</code>, but the program actually prints out <code>left = [3,1]</code>, same for other <code>print</code> statements, why? Thank you very much.</p>

<pre><code>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 &lt; len(left) and j &lt; len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while (i &lt; len(left)):
        result.append(left[i])
        i += 1
    while (j &lt; 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) &lt; 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)
</code></pre>

<hr>

<pre><code>&gt;&gt;&gt; L = [3,1,2,5,4,9,6,7,8]
&gt;&gt;&gt; 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]
</code></pre>

<pre><code>left = mergeSort(L[:middle], compare)
print "left = ", left
right = mergeSort(L[middle:], compare)
print "right = ", right
</code></pre>

<p>This should work.</p>

python recursion mergesort