1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you serious ? Sorting a single number or less !? $\endgroup$
    – user16034
    Sep 5, 2023 at 19:01
  • $\begingroup$ 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. $\endgroup$
    – Pseudonym
    Sep 5, 2023 at 22:23
  • $\begingroup$ 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! $\endgroup$ Sep 5, 2023 at 22:52
  • $\begingroup$ 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. $\endgroup$ Sep 5, 2023 at 22:56

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for explaining the answer at a fundamental level. I understood the significance of sorting algorithm advantages, and just needed some help interpreting this particular result. I knew there would be a crossover point, but I didn't understand why there was two. I realize now the insignificance of the little n, and my incorrect interpretation of the values. Sometimes you just have to ask the dumb questions. $\endgroup$ Sep 5, 2023 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.