Sorting & Searching

Elementary Sorts

Selection, insertion, and bubble sort are all O(n²) — but insertion sort is the one worth actually using: adaptive on nearly-sorted data and the fallback inside every hybrid sort for small partitions.

Selection sort: always O(n²) comparisons, but only O(n) swaps — good when writes are expensive
Insertion sort: O(n) best case on nearly-sorted data; adaptive and stable
Bubble sort: mostly pedagogical — dominated by insertion sort in every practical dimension
All three are in-place, O(1) extra space, and simple enough to hand-verify
Hybrid library sorts (Timsort, dual-pivot quicksort) fall back to insertion sort below a size threshold (~16–47 elements)

The three elementary sorts
Sort	Comparisons	Swaps	Stable	Adaptive
Selection	Θ(n²) always	O(n)	no	no
Insertion	O(n) best, O(n²) worst	O(n) best, O(n²) worst	yes	yes
Bubble	Θ(n²) typical	O(n²)	yes	yes (with early-exit flag)

Insertion sort builds the sorted region one element at a time: each new element is slid backward past everything larger than it. On an already-sorted array that inner loop never runs — a single pass confirms order in O(n). That adaptiveness is why it beats Mergesort and Quicksort on small or nearly-sorted inputs, where their O(n log n) overhead (recursion, allocation, cache misses) costs more than it saves.

Insertion sort

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;
    }
}