Mergesort return no longer in order
<p>I'm not a beginning python coder, but I'm not an advanced one either. The problem will be easier to explain if you can look at what I'm describing. Here's the code I'm seeing the problem in:</p>

<pre><code>import operator

def mergeSort(L, compare = operator.lt):
    if len(L) &lt; 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)

def merge(left, right, compare):
    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
</code></pre>

<p>The merge function works. The final return result is always in order. The problem is that if you take one step forward from the final return result, returning to the return merge(left, right, compare) in mergesort, the returned list L is no longer in order, and then this badly ordered list is returned to the function that called mergesort. I can't even see why this is happening. What could happen on the return trip from return result to return merge(left, right, compare)? The returned list isn't a randomized list, it looks like a partially sorted list, but it was completely sorted at the final return result, and this result was not the one returned to mergesort.</p>

<p>I've used this mergesort before with no problems, so the issue could be in the data I'm sorting. L is a list of lists, and each list element is a list of strings, all the same length, to be exported to csv and eventually to Excel. My data is a table with website titles in the first column and urls in the second column, and I'm sorting them to identify the duplicates. The complete table has several other fields in it, but I see this problem with only the title and url columns, which was what I simplified down to so I could try to see what was going wrong. I wasn't sure if mergesort could handle this data structure, but the final return result in merge certainly indicates that it can. But something mysterious happens in the final return.</p>