Merge Sort
Merge sort uses a strategy called divide and conquer: split the list in half, sort each half (by calling itself), then merge the two sorted halves into one. Merging two sorted lists is easy and fast: compare the front items and take the smaller.
There are about log n levels of splitting and each level does about n work, so merge sort is O(n log n), far faster than O(n squared) for big lists. It needs extra memory for the merged lists.
Examplepython
Quick check
What is the Big O of merge sort?
Your turn: write the code
Merge these two sorted lists into one sorted list (without using sort or sorted) and print it.
Finish the quick check (and any code exercise) to complete this lesson, or mark it done yourself.
Tip: use the left and right arrow keys to move between lessons.