In [3]:
import numpy as np
from IPython.display import clear_output
from pjdiagram import *
from ipywidgets import *
from mergesort import merge_sort_example
| Performance | Complexity |
|---|---|
| Worst-case | $O(n\log{n})$ |
| Best-case | $O(n\log{n})$ |
| Average | $O(n\log{n})$ |
| Worst-case space | $O(n)$ |
Recursively split list and then recursively merge them together in sorted order. Because the merge is done recursively, starting from the individual elements, the lists being merged together are guaranteed to be sorted.
In [4]:
def mergesort(lst):
# this is an individual element
if len(lst) == 1: return lst
# find the midpoint
mid = len(lst)/2
# run mergesort on the left hand side
left = mergesort(lst[:mid])
# run mergesort on the right hand side
right = mergesort(lst[mid:])
# merge sorted lists back together
return merge(left, right)
and to merge the lists back together, we just have to iterate over both lists picking whichever list has the smallest item. To do so, we'll keep two indices: i and j. It's possible one list is larger than the other (i.e. if the list is odd, then when split it will give two differently sized lists):
In [8]:
def merge(left, right):
# indices into left and right lists
i = j = 0
# merged list
result = []
# keep going until we've gone over every element within the list
while i < len(left) or j < len(right):
if i >= len(left):
# if left is empty, use right
result.append(right[j])
j += 1
elif j >= len(right):
# if right is empty, use left
result.append(left[i])
i += 1
elif left[i] < right[j]:
# if left is less than right, use left
result.append(left[i])
i += 1
else:
# otherwise use right
result.append(right[j])
j += 1
return result
Animation of mergesort:
In [7]:
merge_sort_example([5, 2, 1, 20, 10, 3, 4, 80])
Let's try out our code:
In [5]:
lst = [5, 2, 1, 20, 10, 3, 4, 80, 0]
sorted_list = mergesort(lst)
print(sorted_list)