# Comparing sorting algorithms -- Insertion Sort vs. Merge Sort

## Homework Statement:

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 $54n \log_2n$ steps. For which values of n does insertion sort beat merge sort?

## Relevant Equations:

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?

Related Engineering and Comp Sci Homework Help News on Phys.org
.Scott
Homework Helper
It is because sorting a list of 1 item is a no-op and is usually not interesting.
Still, it should have mentioned that exception.

berkeman
rcgldr
Homework Helper
Comparing 8 n^2 versus 54 n ceiling(log2(n)) the change occurs between n = 40 and n = 41.
ceiling log2(n) = 6, for n from 33 to 64 inclusive.
8 · (40^2) = 12800 versus 54 · 40 · 6 = 12960
8 · (41^2) = 13448 versus 54 · 41 · 6 = 13284

Last edited: