Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size , insertion sort runs in steps, while merge sort runs in steps. For which values of does insertion sort beat merge sort?

For insertion sort to beat merge sort for inputs of size , must be less than . $$8n^2 < 64n \lg n \implies \frac n 8 < \lg n \implies 2^{n/8} < n$$

This is not a purely polynomial equation in . To find the required range of values of , either we have to manually calculate the values of these expression for different values of or use Newton’s Method or plot these functions or write a piece of code to found the values. For this exercise, I’ll briefly describe all of these methods but going forward I’ll mostly use calculations that can be done with scientific calculator (to help the students visiting these pages) and python codes (to help myself).


Calculate: It is obvious that insertion sort runs at quadratic time which is definitely worse than merge sort’s linearithmic time for very large values of . We know for , merge sort beats insertion sort. But for values greater than that, insertion sort beats merge sort. So, we will start checking from and go up to see for what value of merge sort again starts to beat insertion sort.

Notice that for , will be a fraction. So, let’s start with and check for values of which are power of 2.

Somewhere between 32 and 64, merge sort starts to beat insertion sort. Let’s do what we were doing but now we are going to try middle value of either range, repeatedly (binary search).

So, at , merge sort starts to beat insertion sort again. Therefore, for , insertion sort beats merge sort.


Newton's Method: To apply Newton’s method of approximation, we need to ballpark two values of on either side of the actual solution and hit-and-try for the actual one following binary search principle. This is the principle we have almost followed in the previous section but the proper process involves calculus and way too time consuming for me to write about.


Graphical Plot: Plot the functions and to get the points where they intersect.

Graph rendered by JSXGraph

From the above graph, we can see that the plots intersect at and . Here, is a input size so it must be an integer. So, the values of for which insertion beats merge sort is .


Python Code: Let’s start with and go up to see for what value of merge sort again starts to beat insertion sort.


If you have any question or suggestion or you have found any error in this solution, please leave a comment below.