Skip to content

Instantly share code, notes, and snippets.

@andrewsosa
Last active March 6, 2017 17:23
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save andrewsosa/82d09aaff41b7888aac60db5c162e4ee to your computer and use it in GitHub Desktop.
Save andrewsosa/82d09aaff41b7888aac60db5c162e4ee to your computer and use it in GitHub Desktop.
Minimalistic Merge sort in Python
def select(left, right):
"""Choose the minimum front from left and right, but handle empty lists."""
return left.pop(0) if (len(left) > 0 and len(right) is 0) or (len(left) > 0 and left[0] < right[0]) else right.pop(0)
def merge(left, right):
"""Conquer: Merge together the selected (min) front of left and right."""
return [select(left,right) for i in range((len(left) + len(right)))]
def sort(l):
"""Divide: Recursive call to split input list into managable sublists."""
return l if len(l) is 1 else merge(sort(l[:len(l)/2]), sort(l[len(l)/2:]))
if __name__ == '__main__':
l = list("aninputstring") # string list
l = [int(s) for s in "8234837"] # integer list
print sort(l)
@glfmn
Copy link

glfmn commented Mar 6, 2017

This is short, well done! I need to get back into python.

Maybe I'll make a haskell equivalent for fun.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment