Divide and Conquer - Mergesort (3/7)

We explore mergesort, a classic divide-and-conquer sorting algorithm. We walk through how mergesort splits a list into smaller pieces, recursively sorts them and combines them into one sorted list. We take a closer look at the merge step, learning why comparing the smallest remaining element from each sorted list lets us merge in O(n) time. We also examine the algorithm's recursive structure, including its base case and how the two halves are combined. We then go through a relatively short example. The key idea is this, we want to sort smaller problems recursively and then combine their solutions efficiently.