マージソート
id:Voluntasとの会話で出てきたので書いてみた
#!/usr/bin/env python def mergesort(a): if len(a) in (0, 1): return a p = len(a)/2 f, b = a[:p],a[p:] return merge(mergesort(f), mergesort(b)) def merge(a, b, result=[]): if len(a) == 0: return result + b elif len(b) == 0: return result + a elif a[-1] < b[0]: return result + a + b elif b[-1] < a[0]: return result + b + a elif a[0] < b[0]: return merge(a[1:], b, result + [a[0]]) else: return merge(a, b[1:], result + [b[0]]) def main(): assert mergesort([]) == [] assert mergesort([0]) == [0] assert mergesort([0, 1]) == [0, 1] assert mergesort([1, 0]) == [0, 1] assert mergesort([2, 0, 1]) == [0, 1, 2] import random dummy = [random.randint(0, 100) for x in xrange(100)] assert mergesort(dummy) == sorted(dummy) assert mergesort(sorted(dummy)) == sorted(dummy) assert mergesort(list(reversed(sorted(dummy)))) == sorted(dummy) if __name__ == '__main__': main()