# Understanding crossover points in efficiency between insertion and merge sorts

Self-taught programmer here. I'm reading CORS, and right at the beginning, question 1.2-2, there asks a question:

For inputs of size $$n$$, insertion sort runs in $$8n^2$$ steps, which merge sort runs in $$64n\lg n$$ steps. Which values of $$n$$ does insertion sort beat merge sort?

I simplified this to $$n=8\lg n$$, and ran it through a CAS, to get two approximations for $$n$$, $$n\approx 1.099$$ and $$n\approx 43.559$$.

I'm unsure how to intrepret these values in relation to the question. My initial assumption is the merge sort is faster for all $$n\geq2$$, but then we get to $$n\geq44$$, and... insertion sort becomes faster than merge sort again? That seems impossible.

My first intuitive answer was that whenever $$n < 8\lg n$$, insertion is faster. However, once I started to try to attain a value, is when I ran into the two roots and couldn't find a clear explanation.

• Are you serious ? Sorting a single number or less !?
– user16034
Sep 5, 2023 at 19:01
• The short answer is that, even if you're using a precise measure of what a "step" is (e.g. counting the number of comparisons), $64 n \log n$ is a continuous approximation to a discrete function. You can't sort $1.099$ items, and sorting $100$ items does not take $42520.68$ steps. Sep 5, 2023 at 22:23
• It was a misunderstanding of what the low n value represented when solving the logarithm, not the approximate values. It is obvious to me now why the low n should be ignored, and why n = 44 is the cross over point. Thanks for your input! Sep 5, 2023 at 22:52
• I get it now. My first interpretation was that at the low n value, merge sort became more efficient, which is why I didn’t understand the high n value. Recognizing now that the low n has no practicality, and that merge sort took over at n = 44, made everything click. Sep 5, 2023 at 22:56

Understand that the purpose of the exercise is to let you realize that there can be crossover points. But the given functions are imaginary and just mean to show trends. (In practice, the expressions are more complicated and low order terms become dominant for low $$n$$.) So don't care about small $$n$$.
Obviously, this MergeSort beats the InsertionSort as of $$n=44$$, and the advantage becomes larger and larger with $$n$$. The main lesson is that $$O(n\log(n))$$ is significantly better than $$O(n^2)$$.