Skip to content

Instantly share code, notes, and snippets.

@aajjbb
Created October 16, 2013 23:41
Show Gist options
  • Save aajjbb/7016897 to your computer and use it in GitHub Desktop.
Save aajjbb/7016897 to your computer and use it in GitHub Desktop.
Python implementation of merge sort
class MergeSort(object):
def __init__(self):
pass
def merge(self, left, right):
ans = []
while left and right:
if left[0] < right[0]:
ans.append(left.pop(0))
else:
ans.append(right.pop(0))
while left:
ans.append(left.pop(0))
while right:
ans.append(right.pop(0))
return ans
def msort(self, array):
if len(array) <= 1:
return array
else:
m = len(array) // 2
l = self.msort(array[:m])
r = self.msort(array[m:])
return self.merge(l, r)
if __name__ == "__main__":
m = MergeSort();
print(m.msort([9, 8, 7, 6, 5, 4, 3, 2, 1]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment