Sorting
Merge sort is a high-performing, moderately-difficult-to-implement sorting algorithm. It has O(n log n) runtime.
Read about Merge sort at https://en.wikipedia.org/wiki/Merge_sort, paying close attention to the pseudocode section “Top-down implementation using lists”.
We’ve provided a file, mergesort.py, with a stub function, merge_sort:
def merge_sort(lst):
"""Divide and conquer: reduce to lists of 0-1 items, then recombine."""
Finish the implementation.