msort

def test(fun):
    lists = [
        [],
        [0],
        [1],
        [-1],
        [3, 3],
        [1, 2],
        [2, 1],
        [2, 2, 2, 2, 2, 3, 5, 5, 6, 7, 12, 34, 54, 66, 643, 233453, 345353],
        [2,3,5,12,54,6,7,643,233453,2,2,345353,2,2,34,5,66],
    ]
    for li in lists:
        if not fun(li) == sorted(li):
            print fun(li), 'is not', sorted(li)
            return False
    return True


def qsort(li):
    if len(li) <= 1:
        return li
    pivot = li[0]
    leq = []
    gt = []
    for elem in li[1:]:
        if elem <= pivot:
            leq.append(elem)
        else:
            gt.append(elem)
    return qsort(leq) + [pivot] + qsort(gt)


def msort(li):
    if len(li) <= 1:
        return li
    mid = len(li) / 2
    first = msort(li[:mid])
    last = msort(li[mid:])
    res = []
    while first and last:
        if first[0] <= last[0]:
            res.append(first.pop(0))
        else:
            res.append(last.pop(0))
    return res + first + last


def msort2(li):
    if len(li) <= 1:
        return li
    mid = len(li) / 2
    first = msort(li[:mid])
    last = msort(li[mid:])
    res = []
    while first and last:
        res.append((first if first[0] <= last[0] else last).pop(0))
    return res + first + last

def msort25(li):
    if len(li) <= 1:
        return li
    mid = len(li) / 2
    first = msort(li[:mid])
    last = msort(li[mid:])
    res = []
    while first or last:
        res.append((first if first and first[0] <= last[0] else last).pop(0))
    return res


def msort3(li):
    if len(li) <= 1:
        return li
    mid = len(li) / 2
    first = msort(li[:mid])
    last = msort(li[mid:])
    res = []
    #while first or last:
    #    res.append((first if first and first[0] <= last[0] else last).pop(0))
    infiter = [1] * len(li)
    res = [(first if first and first[0] <= last[0] else last).pop(0) for t in infiter if first or last]
    return res

def msort4(li):
    #if len(li) <= 1:
    #    return li
    first, last = msort(li[:len(li)/2]), msort(li[len(li)/2:])
    return [(first if first[0] <= last[0] else last).pop(0) for _ in li if first and last] + first + last
    #infiter = li
    #res = [(first if first and (not last or first[0] <= last[0]) else last).pop(0) for _ in infiter if first or last]
    #return [(first if first[0] <= last[0] else last).pop(0) for _ in infiter if first and last] + first + last

print test(msort2)
#print test(msort25)
#print test(msort3)
print test(msort4)