What's wrong with my mergesort implementation?

Question

On smaller lists of up to size N = ~1950 or so, I get the correct output... however, list sizes that are not much larger return an error rather than the expected result. My code:

def merge(left, right, aux=[]):
    if left == []:
        for x in right:
            aux.append(x)
        return aux
    elif right == []:
        for x in left:
            aux.append(x)
        return aux
    elif left[0] > right[0]:
        aux.append(right[0])
        return merge(left, right[1:], aux)
    else:
        aux.append(left[0])
        return merge(left[1:], right, aux)

def msort(values):
    size = len(values)

    if size == 1:
        return values
    else:
        mid = size/2
        return merge(msort(values[:mid]), msort(values[mid:]), [])

Running msort on these test lists give me the expected (ascending order) output:

val = [x for x in range(1950, 0, -1)
val = [x for x in range(4,0,-1)]

e.g. [1,2,3,...,1948,1949,1950] and [1,2,3,4]

However, when I run msort on this test case:

val = [x for x in range(2000,0,-1)]

I now receive this error (after numerous tracebacks to merge):

RuntimeError: maximum recursion depth exceeded in cmp

So my question is: What went wrong with my implementation here? I can't use it with lists of N ~ >=2000. Why?

Answer 1

Your merge function uses recursion that has a limit.

If you iterate instead of recurring you circumvent this:

def merge(left, right, aux=[]):
    while left and right:
        if left[0] > right[0]:
            aux.append(right.pop(0))
        else:
            aux.append(left.pop(0))
    aux.extend(right)
    aux.extend(left)
    return aux

This is an example of the usage:

>>> merge([1,3,5,7], [3,4,5,6])
[1, 3, 3, 4, 5, 5, 6, 7]