When is InsertionSort actually optimal?

Problem. InsertionSort is O(n²) — so when is it actually the optimal choice?

What InsertionSort does

It grows a sorted prefix one element at a time, shifting each new element left into place. The number of shifts equals the number of inversions (out-of-order pairs) in the input — which is the key to when it shines.

void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

When it wins

• Small arrays. For n below ~16–64, its tiny constant factor and zero setup beat the recursion/allocation overhead of MergeSort or Quicksort. This is exactly why production sorts (dual-pivot Quicksort, Timsort) cut over to insertion sort for small subarrays.
• Nearly-sorted data. If the array has d inversions, InsertionSort runs in O(n + d) — effectively O(n) when d is small. On already-sorted input it's a single O(n) pass that does no shifts. This adaptivity is why Timsort uses binary insertion sort to extend short runs.
• Online / streaming. It can sort as elements arrive — insert each new item into the already-sorted prefix — without seeing the whole input first. MergeSort and Quicksort can't.
• Stable and in-place. It preserves equal elements' order and uses O(1) extra space, so it never breaks a multi-key sort.