Skip to content

Instantly share code, notes, and snippets.

@cjrieck
Created December 9, 2013 14:34
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cjrieck/7873072 to your computer and use it in GitHub Desktop.
Save cjrieck/7873072 to your computer and use it in GitHub Desktop.
Merge sort implementation in Python
def merge_sort(aList):
if len(aList) < 2:
return aList
else:
middle = len(aList)/2
left = aList[:middle]
right = aList[middle:]
left = merge_sort(left)
right = merge_sort(right)
return list(merge(left, right))
def merge(left, right):
result = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index+=1
else:
result.append(right[right_index])
right_index+=1
if left:
result.extend(left[left_index:])
if right:
result.extend(right[right_index:])
return result
def main():
myL = [45,1,43,89,2,43,13]
print merge_sort(myL)
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment