Merge Sort in Python
#!/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) + '"' |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment