Last active
March 6, 2017 17:23
-
-
Save andrewsosa/82d09aaff41b7888aac60db5c162e4ee to your computer and use it in GitHub Desktop.
Minimalistic Merge sort in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is short, well done! I need to get back into python.
Maybe I'll make a haskell equivalent for fun.