mergesort.py

def merge(left, right):
    nl = len(left)
    nr = len(right)
    merged = []

    il = 0
    ir = 0
    while il < nl and ir < nr:
        l = left[il]
        r = right[ir]
        if l < r:
            il += 1
            merged.append(l)
        else:
            ir += 1
            merged.append(r)

    return merged + left[il:] + right[ir:]
            

def mergesort(input):
    n = len(input)
    if n < 2:
        return input
    return merge(mergesort(input[0:n/2]), mergesort(input[n/2:]))

mergesort([3, 2, 800, 5, 0, -5])