CLRS 3e 1.2-2

1.2-2 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² steps, while merge sort runs in 64 nlgn steps. For which values of n does insertion sort beat merge sort?

We need to find value of n such that insertion sort runs faster than merge sort so where:

8n² <  64 n lg n       (n > 0)
8n   <  64 lg n           (Obtained by canceling n on both sides)
n     <  8 lg n             (Obtained by diving both sides by 8)

Compute some values

n      8 lg n 

1      0

2      8

10    26.56

20    34.58

30    39.26

40    42.58

50    45.15

We see that 1 doesn't satisfy this condition but n between 10 and 40 definitely do.  At 50, the equation starts to fail again.  We now try values between 40 and 50 to find the exact point where it fails.  This point by brute force is obtained to be at 44.

So we conclude that between [2,43] the insertion sort algorithm runs faster than merge sort.