mergesort.py

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

def mergesort(list):
    if len(list) == 1:
        return list
    left = mergesort(list[0:len(list)/2])
    right = mergesort(list[len(list)/2:len(list)])
    return merge(left, right)

if __name__ == "__main__":
    list = [2, 5, 3, 6, 1, 8, 9]
    print mergesort(list)