- Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in [itex]54n \log_2n [/itex] steps. For which values of n does insertion sort beat merge sort?
- 2^(n/8) < n
The answer says insertion sort runs faster when we're sorting less than 43 items. I agree but with the condition that the first item will not be faster. Why does the answer not mention this? Is it because it is insignificantly faster?