Going through Chapter 2 of CLRS, I was introduced to the concept of divide and conquer, which is a very interesting algorithm technique, and a popular example of the divide and conquer algorithm is merge sort.

Merge sort has an Θ(nlgn) run time, which is very good for large inputs. When the input is sufficiently small enough, the algorithm has a worse run time compared to a sorting algorithm that completes in Θ(n^2) time. One of the exercises is to create an optimized version of the merge sort that runs the original merge sort algorithm for sufficiently larger inputs where it shines and to run insertion sort [ Θ(n^2) ] when the input size is sufficiently small enough. I have a solution for it on my Clio website, this post walks through the process for the solution.