マージソート

import random

def merge_sort(lis):
    l = len(lis)
    if l <= 1:
        return lis
    else:
        h = l/2
        lis1 = lis[0:h]
        lis2 = lis[h:l]
        return merge(merge_sort(lis1), merge_sort(lis2))

def merge(lis1, lis2):
    merged = []
    while True:
        if len(lis1) == 0:
            merged += lis2
            break
        elif len(lis2) == 0:
            merged += lis1
            break
        else:
            if lis1[0] <= lis2[0]:
                merged.append(lis1.pop(0))
            else:
                merged.append(lis2.pop(0))
    return merged


l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", l
l2 = merge_sort(l)
print "sorted: ", l2    

実行例：

^o^ > python merge_sort.py
unsorted: [6, 9, 6, 3, 4, 1, 4, 5, 3, 1, 2, 8, 7, 2, 5, 7, 9, 8]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]