Mergesort is a powerful sorting algorithm that is often used today.

Merge sort is a divide-and-conquer algorithm that recursively divides a list into smaller sublists, sorts those sublists, and then merges them back together in sorted order. It's known for its stable sorting and guarantees a time complexity of O(n log n) in the worst-case scenario.

Mergesort works by using recursion to split an array into roughly two equal size arrays until a base case of array len 0 or 1 is reached. To get to this depth takes time O(log n) Recursion will then travel back up the recursion tree. Instead of splitting an array into two, the algorithm will combine two sub arrays back into one. As it does so, it will sort these sub arrays by iterating though both of them while storing the sorted result. This part is in worst case O(n). Thus the final complexity is O(n log n).

Below is a conceptual depiction of what is happening at each step of the algorithm

It's time to see what the code looks like.

Recursing down to the base case should be fairly straight forward. It may be perplexing what is happening while recursing back up and which variables are storing the sorted results. Let's go into more detail, using the array in the diagram above as input.

At a maximum depth of three, L and R are arrays of len(1). The base case triggers and the function can proceed past the merge_sort lines and start merge. Assume we are at merge([4], [1]). This will return the array [1, 4]. Where will this go? at recursion depth two L is where it is returned to, and is actually larger in size! Similarly R is [5, 8]. These two arrays are sorted again and return into recursion depth one's L with values [1, 4, 5, 8]. This will proceed until all recursions are returned from and the final two arrays can be sorted and returned.

Explaining this is tricky. Try and write out the code yourself and see which parts you remember. By doing it yourself, the concept can be reinforced as well as give a bit of muscle memory. Let's go over a few questions to help reinforce this concept as well.

Practice Questions

Q01. With input merge_sort([8,5,1,2,5]) What is the maximum depth? Assume the first call is at depth zero.

Q02. With an input merge([1, 2], [3, 4]), will the line that is responsible for adding extra elements in B be called?

Q03. With input [4, 3, 2, 1], what is R at depth one? (Note, R is only assigned when recursion is returning up). Assume the first call is at depth zero.

score: 0%