Skip to content

Instantly share code, notes, and snippets.

@yasith
Created April 18, 2012 01:18
Show Gist options
  • Save yasith/2410316 to your computer and use it in GitHub Desktop.
Save yasith/2410316 to your computer and use it in GitHub Desktop.
Merge Sort Python
def msort(L):
if len(L) == 1:
return L
m = len(L)/2
return merge(msort(L[:m]), msort(L[m:]))
def merge(left, right):
BIG = max(left[-1], right[-1]) + 1
left.append(BIG)
right.append(BIG)
L = []
cl = 0
cr = 0
for i in range(len(left) + len(right) - 2):
if left[cl] < right[cr]:
L.append(left[cl])
cl += 1
else:
L.append(right[cr])
cr += 1
return L
print msort([2,1,4,3,6,5,8,7])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment