Every sort so far compares two values at a time, and comparison sorts can't beat O(n log n). Counting sort and radix sort never compare values at all — they use each value (or each digit) as an index. When values are small integers, or have a fixed number of digits, that makes sorting linear.
max, and make a count array of size max + 1, all zeros.x, add one to count[x].count from 0 to max, writing each value v back into the array count[v] times.Count every value, then write the values back in order.
function countingSort(nums) { if (nums.length === 0) return nums; const max = Math.max(...nums); const count = new Array(max + 1).fill(0); for (const x of nums) count[x]++; // how many times each value appears let k = 0; for (let v = 0; v <= max; v++) { while (count[v]-- > 0) nums[k++] = v; // write each value back, count times } return nums;}Time O(n + k), space O(k), where k is the largest value. Brilliant when k is small (ages, grades, letters, digits); hopeless when values reach a billion. Negative values work by shifting everything by the minimum. To sort records by a small key stably, turn the counts into running totals that say where each key's block starts, then place records in order — that version is the building block of radix sort.
Radix sort handles bigger numbers by sorting one digit at a time, from the ones digit up. Each round is a stable bucket pass on a single digit (only 10 buckets), and stability is what makes it work: after sorting by the tens digit, numbers with equal tens digits stay in the order the ones-digit round left them.
One round per digit: drop each number into its digit's bucket, then read the buckets back.
function radixSort(nums) { const max = Math.max(0, ...nums); for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) { const buckets = Array.from({ length: 10 }, () => []); for (const x of nums) buckets[Math.floor(x / exp) % 10].push(x); // stable: keep arrival order nums = buckets.flat(); } return nums;}Time O(d · (n + b)), space O(n + b) for d digits in base b. For 32-bit integers d is fixed, so it's linear in n. Radix sort shines on huge arrays of fixed-width keys — integers, IDs, fixed-length strings.
