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 \(64n \lg n\) steps. For which values of \(n\) does insertion sort beat merge sort?

First of all, \(8n^2 < 64n \lg n\) reduces to \(n < 8 \lg n\). Next I used sort_compare.py to determine when merge sort overtakes insertion sort, which occurs at \(n = 44\). Merge sort is also more effective when \(n = 1\). Therefore, insertion sort beats merge sort when \(1 \lt n \leq 43\).

sort_compare.py:

import math

n = 2
while True:
    if n < 8 * math.log2(n):
        print("for n = " + str(n) + ", insertion sort beats merge sort")
    else:
        print("for n = " + str(n) + ", merge sort wins!")
        break
    n += 1