Skip to content

Instantly share code, notes, and snippets.

@brainkim
Created March 17, 2014 16:54
Show Gist options
  • Save brainkim/9603336 to your computer and use it in GitHub Desktop.
Save brainkim/9603336 to your computer and use it in GitHub Desktop.
Purely functional merge sort in python
def merge(chunk1, chunk2):
if len(chunk1) == 0:
return chunk2
elif len(chunk2) == 0:
return chunk1
else:
c1 = chunk1[0]
c2 = chunk2[0]
if c1 < c2:
return [c1] + merge(chunk1[1:], chunk2)
else:
return [c2] + merge(chunk1, chunk2[1:])
def partition(l, i):
return [l[0:i], l[i:len(l)]]
def merge_sort(l):
if len(l) == 1:
return l
else:
a, b = partition(l, len(l)/2)
return merge(merge_sort(a), merge_sort(b))
merge_sort([5,4,5,1,6,7,4])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment