Skip to content

Instantly share code, notes, and snippets.

@kratorado
Created March 2, 2014 10:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kratorado/9304908 to your computer and use it in GitHub Desktop.
Save kratorado/9304908 to your computer and use it in GitHub Desktop.
This is a demo for merge sort
# This is a demo for merge sort
# Coded according to pseudocode from Introduction.to.Algorithm
INF = float('inf')
def merge(lst, p, q, r):
left = lst[p:q + 1]
left.append(INF)
right = lst[q + 1:r + 1]
right.append(INF)
i = j = 0
for k in range(p, r + 1):
if left[i] <= right[j]:
lst[k] = left[i]
i += 1
else:
lst[k] = right[j]
j += 1
def merge_sort(lst, p, r):
if p < r:
q = (p + r) / 2
merge_sort(lst, p, q)
merge_sort(lst, q + 1, r)
merge(lst, p, q, r)
if __name__ == '__main__':
lst = [5,2,4,7,9,1,3,2,6]
merge_sort(lst, 0, len(lst) - 1)
#merge(lst, 0, 1, 2)
print lst
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment