1
$\begingroup$

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n\in\mathbb{N}$, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n\log(n)$ steps. For which values of $n$ does insertion sort beat merge sort?

  • 1
    It's equivalent to solving n<8\log(n). Assuming the logarithm is 2-based, if $2\leq n\leq 32$, the inequality holds. The exact range can be approximated numerically.2012-03-01

1 Answers 1

2

Solving $8n^2 \lt 64n\log(n)$ (equivalently, $n\lt 8\log(n)$) exactly requires use of Lambert's W function. Solving it approximately is pretty easy.

At $n=1$, $8n^2\gt 64n\log(n)$; at $n=2$, $8n^2 \lt 64n\log(n)$; if $\log$ is base $2$, then they cross again at about $n=45$.