Sorting & Searching

Linear-Time Sorting

Counting sort, radix sort, and bucket sort beat the Ω(n log n) comparison-sort lower bound by never comparing keys at all — they exploit structure in the keys instead, at the cost of generality.

Every comparison-based sort has an information-theoretic Ω(n log n) lower bound (a decision tree distinguishing n! orderings needs log₂(n!) ≈ n log n comparisons)
Counting sort: O(n + k) for integer keys in a small range [0, k) — tally counts, then place directly
Radix sort: sorts by one digit/byte at a time with a stable sub-sort, O(d·(n + k)) for d digits
Bucket sort: distributes into buckets assuming roughly uniform input, then sorts each bucket
All three trade "works on any comparable type" for "works on this key structure, fast"

Choosing a linear-time sort
Sort	Complexity	Assumes
Counting	O(n + k)	integer keys in a known small range [0, k)
Radix (LSD)	O(d·(n + k))	fixed-width keys (digits, bytes, fixed-length strings)
Bucket	O(n) expected	roughly uniform distribution over the key range

Counting sort

static int[] countingSort(int[] a, int maxValue) {
    int[] counts = new int[maxValue + 1];
    for (int x : a) counts[x]++;
    for (int i = 1; i <= maxValue; i++) counts[i] += counts[i - 1];   // prefix sums -> positions
    int[] out = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--) {                          // right-to-left keeps it stable
        out[--counts[a[i]]] = a[i];
    }
    return out;
}