Skip to content

Instantly share code, notes, and snippets.

@aruhier
Created August 17, 2017 15:05
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 aruhier/d6bad8b49f7fc52eda06610e029ad7ce to your computer and use it in GitHub Desktop.
Save aruhier/d6bad8b49f7fc52eda06610e029ad7ce to your computer and use it in GitHub Desktop.
merge sort
#!/usr/bin/env python3
EXAMPLE = [40, 3, 5, 10, -2]
def merge_sort(lst):
if len(lst) < 2:
return lst
elif len(lst) == 2:
return [min(lst), max(lst)]
left_part, right_part = lst[:int(len(lst)/2)], lst[int(len(lst)/2):]
sorted_left_part = merge_sort(left_part)
sorted_right_part = merge_sort(right_part)
last_insertion_index = 0
for i in sorted_left_part:
last_insertion_index = put_and_sort_item_in(
i, sorted_right_part, start_at=last_insertion_index
)
return sorted_right_part
def put_and_sort_item_in(item, lst, start_at=0):
lst_slice = lst[start_at:]
for i, v in enumerate(lst_slice):
if item <= v:
lst.insert(i + start_at, item)
return i
lst.append(item)
return len(lst) - 1
print(merge_sort(EXAMPLE))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment