When n² Beats n log n

Problem

Every production sort (C's qsort in glibc, Java's Arrays.sort, Python's Timsort, Go's sort.Slice) contains an O(n²) algorithm that runs on small or nearly-sorted inputs. Explain why an O(n²) algorithm can beat an O(n log n) one, identify the conditions under which it does, and implement a hybrid merge sort that switches to insertion sort below a cutoff. Then state how you would choose the cutoff and prove the hybrid is still O(n log n) overall.

• Your insertion_sort must be stable and sort a slice in place.
• The hybrid must accept any cutoff, including 0 (pure merge sort) and a cutoff larger than n (pure insertion sort).

Examples

• n = 8, random order. Insertion sort does at most 28 comparisons and 28 moves, all in one cache line, with a trivially predictable loop. Merge sort does about 17 comparisons but also allocates a buffer, makes 15 recursive calls (7 of which merge), and copies 24 elements. The quadratic algorithm wins by a comfortable margin.
• n = 10⁶, random order. Insertion sort does about 2.5 × 10¹¹ moves: minutes. Merge sort does about 2 × 10⁷ comparisons: tens of milliseconds. The n log n algorithm wins by four orders of magnitude.
• n = 10⁶, already sorted except for 50 elements each displaced by a few positions. Insertion sort does about 10⁶ + a few hundred moves: linear. Merge sort still does 2 × 10⁷ comparisons. The quadratic algorithm wins again, because its cost is really O(n + inversions).

Hints

1. Write the actual cost as c₁ · n² versus c₂ · n log n. For which n is the first smaller, given that c₁ is much smaller than c₂?
2. Insertion sort's inner loop stops as soon as it finds the right slot. What is its cost as a function of the number of inversions in the input?
3. If merge sort recurses down to size 1, how many of its calls handle arrays of size ≤ 16? What fraction of the total work is that?