Skip to content

Instantly share code, notes, and snippets.

@AnimeshShaw
Created February 18, 2014 12:46
Show Gist options
  • Select an option

  • Save AnimeshShaw/9070278 to your computer and use it in GitHub Desktop.

Select an option

Save AnimeshShaw/9070278 to your computer and use it in GitHub Desktop.
Merge Sort implementation in python
def merge(left, right):
result = []
n, m = 0, 0
while n < len(left) and m < len(right):
if left[n] <= right[m]:
result.append(left[n])
n += 1
else:
result.append(right[m])
m += 1
result += left[n:]
result += right[m:]
return result
def sort(seq):
if len(seq) <= 1:
return seq
middle = len(seq) / 2
left = sort(seq[:middle])
right = sort(seq[middle:])
return merge(left, right)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment