Merge Sort in Python

mergesort.py

#!/usr/bin/env python

"""
An implementation in python, inspired by the haskell version via
Cormen
(https://github.com/dpapathanasiou/algorithms-unlocked-haskell/blob/master/algorithms-for-sorting-and-searching/MergeSort.hs)

"""

def merge (a, b, c=[]):
    if len(a) == 0:
        return c + b
    elif len(b) == 0:
        return c + a
    else:
        ah = a[0]
        bh = b[0]
        if ah <= bh:
            return merge (a[1:], b, c + [ah])
        else:
            return merge (a, b[1:], c + [bh])

def mergesort (a):
    l = len(a)
    if l < 2:
        return a
    else:
        m = l // 2   
        return merge(mergesort(a[0:m]), mergesort(a[m:]))
        
"""
Test it, using two types of arrays:

1 - a numeric array
2 - a string (array of chars)
"""

narr = [10,2,5,3,1,6,7,4,2,3,4,8,9]
nexp = [1,2,2,3,3,4,4,5,6,7,8,9,10]

nres = mergesort(narr)
print 'sorting', narr, '->', nres
assert nres == nexp, 'expected ' + nexp + ' from sorting ' + narr + ' but got ' + nres

# using list() to keep the type system happy
sarr = list("the quick brown fox jumps over the lazy dog")
sexp = list("        abcdeeefghhijklmnoooopqrrsttuuvwxyz")

sres = mergesort(sarr)
print 'sorting "' + ''.join(sarr) + '" -> "' + ''.join(sres) + '"'
assert sres == sexp, 'expected "' + ''.join(sexp) + '" from sorting "' + ''.join(sarr) + '" but got "' + ''.join(sres) + '"'