Skip to content

Instantly share code, notes, and snippets.

@samueltcsantos
Created February 4, 2015 20:12
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 samueltcsantos/5a9b4bea815d968c4b32 to your computer and use it in GitHub Desktop.
Save samueltcsantos/5a9b4bea815d968c4b32 to your computer and use it in GitHub Desktop.
Mergesort recursive implementation in python
""" Merge Sort Algorithm
Author : Samuel T. C. Santos
version python 3.x
"""
"""
Method that perform the merge operation with two lists.
"""
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j] :
result.append(left[i])
i = i + 1
else:
result.append(right[j])
j = j + 1
while i < len(left):
result.append(left[i])
i = i + 1
while j < len(right):
result.append(right[j])
j = j + 1
return result
"""
Mergesort algorithm recursive implementation.
"""
def mergesort(l):
print(l)
if len(l) < 2:
return l[:]
else:
middle = len(l) // 2
left = mergesort(l[:middle])
right = mergesort(l[middle:])
together = merge(left, right)
print('Merged ', together)
return together
"""
Sample example of execution :
"""
numbers = [2,0,9,6,4,3,5,8,1,7]
ordered = mergesort(numbers)
print(ordered)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment