マージソート

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()