Insertion sort: the hand of cards

Keep the left side sorted as you grow

Insertion sort is how people actually sort a small hand of playing cards. At each step, the left portion is already sorted and you pick up the next card, sliding it left until it lands in the right place. On nearly sorted inputs it is shockingly fast — linear in the number of inversions — and it is the sort library implementations switch to once sub-arrays get small enough.

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

Why it scales the way it does

The running time is Θ(n + I) where I is the number of inversions in the input. Already sorted? I = 0, linear time. Reverse sorted? I = n(n−1)/2, Θ(n²). This is why real-world sorts (Java's Dual-Pivot Quicksort, Python's Timsort) fall back to insertion sort for small or nearly sorted ranges.