Skip to content

Instantly share code, notes, and snippets.

@ddrone
Created June 12, 2012 20:02
Show Gist options
  • Save ddrone/2919790 to your computer and use it in GitHub Desktop.
Save ddrone/2919790 to your computer and use it in GitHub Desktop.
Mergesort implementation in Python
def merge(ls, left, mid, right):
it1 = 0
it2 = 0
result = [0] * (right - left)
while left + it1 < mid and mid + it2 < right:
if ls[left + it1] < ls[mid + it2]:
result[it1 + it2] = ls[left + it1]
it1 += 1
else:
result[it1 + it2] = ls[mid + it2]
it2 += 1
while left + it1 < mid:
result[it1 + it2] = ls[left + it1]
it1 += 1
while mid + it2 < right:
result[it1 + it2] = ls[mid + it2]
it2 += 1
for i in range(it1 + it2):
ls[left + i] = result[i]
def mergesort(ls, left, right):
if left + 1 >= right:
return
mid = (left + right) / 2
mergesort(ls, left, mid)
mergesort(ls, mid, right)
merge(ls, left, mid, right)
ls = [1, 0, 4, 2, 7, 8, 3, 5]
mergesort(ls, 0, len(ls))
print ls
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment