Skip to content

Instantly share code, notes, and snippets.

@flengyel
Created November 14, 2013 03:15
Show Gist options
  • Save flengyel/7460747 to your computer and use it in GitHub Desktop.
Save flengyel/7460747 to your computer and use it in GitHub Desktop.
Merge sort in python
def __merge(a, lo, hi):
"""__merge(a,lo,hi) merge sorts array a from
index lo to index hi, where 0<=lo <= hi < len(a)."""
if lo < hi:
m = (lo+hi)/2
__merge(a,lo,m)
__merge(a,m+1,hi)
b = a[lo:m+1]
c = a[m+1:hi+1]
i = j = 0;
for k in range(lo,hi+1):
if i < len(b) and (j == len(c) or b[i] < c[j]):
a[k] = b[i]
i +=1
else:
a[k] = c[j]
j +=1
def mergesort(a):
__merge(a, 0, len(a)-1)
if __name__ == '__main__':
from random import shuffle
a = range(120)
for i in range(10):
print 'trial ', i+1
shuffle(a)
print(a)
mergesort(a)
print(a)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment