Small Array Optimization — Why Insertion Sort Wins for Small N

The Small Array Paradox

O(n log n) algorithms like Quick Sort and Merge Sort are asymptotically faster than O(n²) algorithms, but for small arrays, the simpler O(n²) algorithms are actually faster in wall-clock time. This is why every production sorting implementation uses a hybrid approach.

Why Simple Algorithms Win for Small N

The actual running time of an algorithm is T(n) = c * f(n) where c is the constant factor and f(n) is the complexity function. For small n:

Insertion Sort: T(n) = c₁ * n²
Merge Sort:     T(n) = c₂ * n * log(n)

But c₁ is much smaller than c₂ because:

1. No recursion overhead: Insertion Sort uses a simple loop, avoiding function call overhead
2. No auxiliary memory: No allocation or copying of temporary arrays
3. Better cache behavior: Sequential memory access pattern
4. Simpler branching: Fewer conditional branches means better branch prediction
5. No divide step: Merge Sort's divide and merge steps have overhead even for small arrays

The Crossover Point

Implementation	Crossover	Threshold Used
Python (Timsort)	~32-64 elements	64 (MIN_RUN)
Java (Arrays.sort)	~47 elements	47
C++ (libstdc++)	~16 elements	16 (_S_threshold)
V8 JavaScript	~10 elements	10
.NET	~16 elements	16

How Hybrid Algorithms Work

function hybridSort(arr, low, high):
  if high - low < THRESHOLD:
    insertionSort(arr, low, high)  // simple algorithm for small subarrays
    return
  // Quick Sort / Merge Sort for larger subarrays
  pivot = partition(arr, low, high)
  hybridSort(arr, low, pivot - 1)
  hybridSort(arr, pivot + 1, high)

Measuring the Crossover

The exact crossover point depends on hardware, compiler optimizations, and data types. To find it for your specific environment:

1. Benchmark Insertion Sort vs Quick Sort for n = 5, 10, 15, 20, 25, 30, 40, 50
2. Find the n where Quick Sort first becomes faster
3. Use that value (minus a margin) as the threshold

Typically the crossover is between 10 and 64 elements, with 16-32 being the most common choice.