Hackbright Code Challenges

Merge Sort

Merge Sort

Whiteboard

Harder

Challenge

Medium

Concepts

Sorting

Download

merge-sort.zip

Solution

Merge Sort: Solution


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.