Every sort so far — quicksort, heap sort, merge sort — decides order by comparing two elements at a time. There’s a proven floor on how fast that can ever go:

is the best any comparison-based sort can guarantee, because sorting must distinguish between $n!$ possible orderings, and each comparison only answers a yes/no question — you need $\log_2(n!) = \Theta(n \log n)$ of them in the worst case. Counting, radix, and bucket sort sidestep this entirely: they never compare two elements to each other. Instead they use the values themselves — as array indices — which unlocks $O(n)$-ish time, if the keys are the right shape (bounded integers, or a range you can bucket).

What you’ll learn

• Counting sort: count occurrences, prefix-sum them into positions, place elements directly — $O(n + k)$, and stable if done carefully.
• Radix sort (LSD): repeatedly counting-sort by one digit at a time, least-significant first, to sort integers of any size in linear time.
• Bucket sort: scatter into ranged buckets, sort each bucket small, then concatenate — great for uniformly distributed values.
• When each one is (and isn’t) the right tool.

Counting sort: count, then place

Counting sort works when every value is a small non-negative integer in a known range 0..k0..k. The idea: count how many times each value appears, turn those counts into prefix sums (so count[v]count[v] becomes “how many elements are $\le v$”), and use that number as each element’s landing spot in the output.

def counting_sort(arr):
    if not arr:
        return arr
 
    k = max(arr)                # values are 0..k
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1
 
    for i in range(1, k + 1):
        count[i] += count[i - 1]   # count[v] = number of elements <= v
 
    output = [0] * len(arr)
    for x in reversed(arr):        # reversed = keeps equal elements stable
        count[x] -= 1
        output[count[x]] = x
 
    return output
 
 
arr = [4, 2, 2, 8, 3, 3, 1]
print("input: ", arr)
print("sorted:", counting_sort(arr))

def counting_sort(arr):
    if not arr:
        return arr
 
    k = max(arr)                # values are 0..k
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1
 
    for i in range(1, k + 1):
        count[i] += count[i - 1]   # count[v] = number of elements <= v
 
    output = [0] * len(arr)
    for x in reversed(arr):        # reversed = keeps equal elements stable
        count[x] -= 1
        output[count[x]] = x
 
    return output
 
 
arr = [4, 2, 2, 8, 3, 3, 1]
print("input: ", arr)
print("sorted:", counting_sort(arr))

Three linear passes over the data (count, prefix-sum, place) — no comparisons anywhere. That’s the whole $O(n + k)$: $n$ for the array, $k$ for the count array covering the value range.

Watch counting sort place each element

Radix sort: counting sort, one digit at a time

Counting sort’s weakness: if the values span a huge range (say, up to a billion), kk is huge and the count array becomes impractically large. Radix sort fixes that by never counting-sorting on the whole value — only on one digit at a time (base 10, so each digit only needs a count array of size 10), starting from the least significant digit (LSD) and working toward the most significant.

def counting_sort_by_digit(arr, exp):
    """Stable counting sort keyed on the digit at place value `exp`
    (exp = 1 for ones, 10 for tens, 100 for hundreds, ...)."""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
 
    for x in arr:
        digit = (x // exp) % 10
        count[digit] += 1
 
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    for x in reversed(arr):        # reversed again -- stability matters here too
        digit = (x // exp) % 10
        count[digit] -= 1
        output[count[digit]] = x
 
    return output
 
 
def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr
 
 
nums = [170, 45, 75, 90, 802, 24, 2, 66]
print("sorted:", radix_sort(nums))

def counting_sort_by_digit(arr, exp):
    """Stable counting sort keyed on the digit at place value `exp`
    (exp = 1 for ones, 10 for tens, 100 for hundreds, ...)."""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
 
    for x in arr:
        digit = (x // exp) % 10
        count[digit] += 1
 
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    for x in reversed(arr):        # reversed again -- stability matters here too
        digit = (x // exp) % 10
        count[digit] -= 1
        output[count[digit]] = x
 
    return output
 
 
def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr
 
 
nums = [170, 45, 75, 90, 802, 24, 2, 66]
print("sorted:", radix_sort(nums))

For $d$ digits and $n$ numbers, that’s $d$ passes of an $O(n + 10)$ counting sort each — $O(d \cdot n)$ total, which is linear in $n$ for any fixed number of digits (i.e., fixed-width integers, like 32-bit or 64-bit).

Bucket sort: scatter, sort small, concatenate

Bucket sort targets values uniformly spread across a known range (the classic case: floats in [0, 1)[0, 1)). Scatter each value into one of kk equal-width buckets by its magnitude, sort each (small) bucket with whatever comparison sort you like, then concatenate the buckets in order.

def bucket_sort(arr, bucket_count=10):
    if not arr:
        return arr
 
    buckets = [[] for _ in range(bucket_count)]
    for x in arr:
        idx = int(x * bucket_count)
        idx = min(idx, bucket_count - 1)   # guard x == 1.0 landing out of range
        buckets[idx].append(x)
 
    for b in buckets:
        b.sort()   # each bucket is small -- even O(n^2) insertion sort is fine here
 
    result = []
    for b in buckets:
        result.extend(b)
    return result
 
 
data = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print("sorted:", bucket_sort(data))

def bucket_sort(arr, bucket_count=10):
    if not arr:
        return arr
 
    buckets = [[] for _ in range(bucket_count)]
    for x in arr:
        idx = int(x * bucket_count)
        idx = min(idx, bucket_count - 1)   # guard x == 1.0 landing out of range
        buckets[idx].append(x)
 
    for b in buckets:
        b.sort()   # each bucket is small -- even O(n^2) insertion sort is fine here
 
    result = []
    for b in buckets:
        result.extend(b)
    return result
 
 
data = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print("sorted:", bucket_sort(data))

If the input really is uniformly distributed, every bucket ends up with roughly n / kn / k elements, so sorting all buckets costs $O(n)$ total on average — the $O(n \log n)$ (or worse) inner sorts are each working on a tiny slice. If the data is instead heavily clustered into one bucket, you’re back to sorting almost the whole array with one comparison sort, and the worst case becomes $O(n^2)$.

When these are (and aren’t) the right tool

• Counting sort: values are small non-negative integers with a known, small range kk (e.g., ages, grades, byte values 0-255). Bad idea if kk is huge relative to nn — you’d allocate a giant, mostly-empty array.
• Radix sort: fixed-width integers (or strings treated digit-by-digit) of any magnitude — the digit count dd stays small (10 for a billion) even when the values themselves are huge.
• Bucket sort: values you know are roughly uniformly distributed over a range — floats in [0, 1)[0, 1), timestamps spread across a day, etc. Clustered/skewed data defeats it.
• None of these three handle arbitrary comparable objects (strings by dictionary order, custom objects) as directly as sorted()sorted() does — that’s what the next lesson, Timsort and custom sorting, covers.

Complexity at a glance

kk = value range (counting sort) or bucket count (bucket sort); dd = number of digits; bb = digit base (10 for decimal digits).

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 1122 — Relative Sort Array · Easy

Problem. Sort arr1arr1 so that its elements follow the relative order given by arr2arr2. Elements not present in arr2arr2 go at the end, in ascending order.

Constraints. 1 <= len(arr1), len(arr2) <= 10001 <= len(arr1), len(arr2) <= 1000, 0 <= values <= 10000 <= values <= 1000, arr2arr2 has distinct values, all of which appear in arr1arr1.

Examples. arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] gives [2,2,2,1,4,3,3,9,6,7,19][2,2,2,1,4,3,3,9,6,7,19]

LC 274 — H-Index · Medium

Problem. Given citation counts for a researcher’s papers, return their h-index: the largest hh such that at least hh papers have at least hh citations each.

Constraints. 1 <= len(citations) <= 50001 <= len(citations) <= 5000, 0 <= citations[i] <= 10000 <= citations[i] <= 1000.

Examples. [3,0,6,1,5][3,0,6,1,5] gives 33 · [1,3,1][1,3,1] gives 11 · [100][100] gives 11

LC 164 — Maximum Gap · Medium

Problem. Return the maximum difference between two successive elements in the array’s sorted form. If the array has fewer than two elements, return 00. Aim for linear time and space.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, 0 <= nums[i] <= 10^90 <= nums[i] <= 10^9.

Examples. [3,6,9,1][3,6,9,1] gives 33 · [10][10] gives 00

Recap

• Comparison sorts are stuck at $\Omega(n \log n)$ — a proven lower bound. Counting, radix, and bucket sort escape it by using key values directly as positions, never comparing elements to each other.
• Counting sort ($O(n + k)$): count, prefix-sum into positions, place in reverse for stability. Needs a small integer range kk.
• Radix sort ($O(d(n+b))$): repeated stable counting sort, one digit at a time, LSD first — correctness depends on every pass being stable.
• Bucket sort ($O(n+k)$ average): scatter into ranged buckets, sort each small bucket, concatenate — shines on uniformly distributed data, degrades to $O(n^2)$ if the data clusters into one bucket.

Next: Timsort and Custom Sorting — how Python’s built-in sorted()sorted() and .sort().sort() actually work, and how to sort arbitrary objects with key=key= and custom comparators.