Counting, Radix, and Bucket Sort: Beyond O(n log n)

Every comparison-based sorting algorithm — merge sort, quick sort, heap sort — has a lower bound of O(n log n). This is a proven mathematical fact: you cannot determine the order of n elements with fewer than n log n comparisons in the worst case. But what if you do not compare elements at all? Counting sort, radix sort, and bucket sort bypass comparisons entirely, achieving O(n) or near-linear time under the right conditions.

---

1. The Comparison Sort Lower Bound

Any comparison sort builds a decision tree where each internal node is a comparison and each leaf is a permutation of the input. With n! permutations, the tree needs at least log(n!) = O(n log n) levels. You cannot do better with comparisons.

But non-comparison sorts exploit the structure of the keys (their digits, ranges, or buckets) to sort without pairwise comparisons.

---

2. Counting Sort

When to use: the values are integers in a known, small range [0, k).

Idea: count how many times each value appears, then place them in order.

def counting_sort(arr, max_val=None):
    """
    Sort an array of non-negative integers using counting sort.

    Time: O(n + k) where k = max value + 1
    Space: O(n + k)
    Stable: Yes

    Args:
        arr: list of non-negative integers
        max_val: maximum value (computed if not given)

    Returns:
        Sorted array.
    """
    if not arr:
        return []

    if max_val is None:
        max_val = max(arr)

    k = max_val + 1

    # Step 1: Count occurrences
    count = [0] * k
    for num in arr:
        count[num] += 1

    # Step 2: Compute cumulative counts (prefix sums)
    for i in range(1, k):
        count[i] += count[i - 1]

    # Step 3: Build output array (iterate right-to-left for stability)
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        val = arr[i]
        count[val] -= 1
        output[count[val]] = val

    return output


print(counting_sort([4, 2, 2, 8, 3, 3, 1]))
# Output: [1, 2, 2, 3, 3, 4, 8]

print(counting_sort([0, 0, 1, 1, 0, 1]))
# Output: [0, 0, 0, 1, 1, 1]

Simplified Version (When Stability Is Not Needed)

def counting_sort_simple(arr):
    """Simpler counting sort — just count and expand."""
    if not arr:
        return []

    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    result = []
    for val in range(len(count)):
        result.extend([val] * count[val])

    return result


print(counting_sort_simple([4, 2, 2, 8, 3, 3, 1]))
# [1, 2, 2, 3, 3, 4, 8]

Counting Sort with Negative Numbers

def counting_sort_with_negatives(arr):
    """Handle negative integers by shifting."""
    if not arr:
        return []

    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1

    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1

    result = []
    for i in range(range_size):
        result.extend([i + min_val] * count[i])

    return result


print(counting_sort_with_negatives([-3, 2, -1, 0, 3, -3, 1]))
# [-3, -3, -1, 0, 1, 2, 3]

When Counting Sort Shines

• Range of values k is O(n) or smaller.
• Used as a subroutine in radix sort.
• Sorting exam scores (0-100), ASCII characters, ages, etc.

When to Avoid

• k is very large (e.g., sorting 64-bit integers by value — would need 2^64 buckets).
• Floating-point numbers (need bucket sort instead).

---

3. Radix Sort — LSD (Least Significant Digit)

When to use: sorting integers or fixed-length strings by processing one digit/character at a time, from least significant to most significant.

Key requirement: the subroutine sort (for each digit) must be stable — counting sort is the standard choice.

def radix_sort_lsd(arr):
    """
    Sort non-negative integers using LSD radix sort.

    Time: O(d * (n + b)) where d = number of digits, b = base (10)
    Space: O(n + b)
    Stable: Yes

    Uses base-10 digits. Process from least significant to most significant.
    """
    if not arr:
        return []

    max_val = max(arr)

    # Sort by each digit, starting from the least significant
    exp = 1  # current digit place (1s, 10s, 100s, ...)
    result = arr[:]

    while max_val // exp > 0:
        result = _counting_sort_by_digit(result, exp)
        exp *= 10

    return result


def _counting_sort_by_digit(arr, exp):
    """
    Stable sort by the digit at position `exp`.
    E.g., exp=1 sorts by ones digit, exp=10 by tens digit.
    """
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # digits 0-9

    # Count occurrences of each digit
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1

    # Cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build output (right-to-left for stability)
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        count[digit] -= 1
        output[count[digit]] = arr[i]

    return output


print(radix_sort_lsd([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

print(radix_sort_lsd([329, 457, 657, 839, 436, 720, 355]))
# [329, 355, 436, 457, 657, 720, 839]

Why LSD Works

Processing digits from right to left seems backwards, but stability is the key. After sorting by the ones digit, all numbers with the same ones digit are in the right relative order. When we then sort by the tens digit (stably), numbers with the same tens digit retain their ones-digit order. By the time we finish the most significant digit, everything is sorted.

---

4. Radix Sort — MSD (Most Significant Digit)

MSD radix sort processes from the most significant digit first. It works like a recursive bucket sort.

def radix_sort_msd(arr):
    """
    Sort non-negative integers using MSD radix sort.

    Time: O(d * (n + b))
    Space: O(n + b) per recursion level

    Processes from most significant digit to least significant.
    """
    if not arr:
        return []

    max_val = max(arr)
    max_digits = len(str(max_val))

    def _msd_sort(arr, digit_pos):
        """Sort arr by the digit at digit_pos (0 = most significant)."""
        if len(arr) <= 1 or digit_pos >= max_digits:
            return arr

        # Create 10 buckets (one per digit 0-9)
        buckets = [[] for _ in range(10)]

        divisor = 10 ** (max_digits - 1 - digit_pos)
        for num in arr:
            digit = (num // divisor) % 10
            buckets[digit].append(num)

        # Recursively sort each bucket by next digit
        result = []
        for bucket in buckets:
            if len(bucket) > 1:
                result.extend(_msd_sort(bucket, digit_pos + 1))
            else:
                result.extend(bucket)

        return result

    return _msd_sort(arr, 0)


print(radix_sort_msd([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

LSD vs MSD

Property	LSD	MSD
Direction	Right to left	Left to right
Stability	Naturally stable	Stable within buckets
Best for	Fixed-length keys	Variable-length strings
Parallelism	Hard	Natural (independent buckets)
Short-circuit	No	Yes (single-element buckets)

---

5. Radix Sort for Strings

Radix sort is excellent for sorting strings of equal length (like zip codes, dates, etc.).

def radix_sort_strings(strings, max_len=None):
    """
    Sort fixed-length strings using LSD radix sort.

    Time: O(d * (n + 256)) where d = string length
    Space: O(n)
    """
    if not strings:
        return []

    if max_len is None:
        max_len = max(len(s) for s in strings)

    # Pad shorter strings with null characters
    padded = [s.ljust(max_len, '\0') for s in strings]

    result = padded[:]

    # Process from rightmost character to leftmost
    for pos in range(max_len - 1, -1, -1):
        # Counting sort by character at position `pos`
        count = [0] * 256
        for s in result:
            count[ord(s[pos])] += 1

        for i in range(1, 256):
            count[i] += count[i - 1]

        output = [''] * len(result)
        for i in range(len(result) - 1, -1, -1):
            c = ord(result[i][pos])
            count[c] -= 1
            output[count[c]] = result[i]

        result = output

    # Remove padding
    return [s.rstrip('\0') for s in result]


words = ["cat", "bat", "ant", "car", "bar", "art"]
print(radix_sort_strings(words))
# ['ant', 'art', 'bar', 'bat', 'car', 'cat']

---

6. Bucket Sort

When to use: values are uniformly distributed over a known range (often floating-point numbers in [0, 1)).

Idea: distribute elements into k buckets, sort each bucket (with insertion sort or any sort), and concatenate.

def bucket_sort(arr, num_buckets=10):
    """
    Sort floating-point numbers in [0, 1) using bucket sort.

    Time: O(n + k) average (when distribution is uniform)
    Space: O(n + k)
    Stable: Depends on subroutine sort

    Worst case: O(n^2) if all elements land in one bucket.
    """
    if not arr:
        return []

    n = len(arr)
    buckets = [[] for _ in range(num_buckets)]

    # Distribute elements into buckets
    for num in arr:
        idx = int(num * num_buckets)
        # Handle edge case: num == 1.0
        if idx == num_buckets:
            idx -= 1
        buckets[idx].append(num)

    # Sort each bucket (insertion sort for small buckets)
    for bucket in buckets:
        bucket.sort()  # or use insertion sort

    # Concatenate
    result = []
    for bucket in buckets:
        result.extend(bucket)

    return result


data = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print(bucket_sort(data))
# [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

Bucket Sort for Integers

def bucket_sort_integers(arr, num_buckets=10):
    """
    Bucket sort for integers over an arbitrary range.
    """
    if not arr:
        return []

    min_val = min(arr)
    max_val = max(arr)

    if min_val == max_val:
        return arr[:]

    range_size = max_val - min_val + 1
    bucket_size = max(1, range_size // num_buckets + 1)

    buckets = [[] for _ in range(num_buckets + 1)]

    for num in arr:
        idx = (num - min_val) // bucket_size
        buckets[idx].append(num)

    result = []
    for bucket in buckets:
        bucket.sort()
        result.extend(bucket)

    return result


print(bucket_sort_integers([29, 25, 3, 49, 9, 37, 21, 43]))
# [3, 9, 21, 25, 29, 37, 43, 49]

Maximum Gap Problem (Bucket Sort Application)

def maximum_gap(nums):
    """
    LeetCode 164: Maximum Gap.

    Find the maximum difference between successive elements
    in the sorted form, in O(n) time.

    Key insight: use bucket sort. The maximum gap must be >= ceil((max-min)/(n-1)).
    So if we use buckets of that size, the max gap is between buckets, not within.
    """
    n = len(nums)
    if n < 2:
        return 0

    min_val, max_val = min(nums), max(nums)
    if min_val == max_val:
        return 0

    # Bucket size: gap between buckets >= this value
    bucket_size = max(1, (max_val - min_val) // (n - 1))
    num_buckets = (max_val - min_val) // bucket_size + 1

    # Each bucket stores only min and max
    bucket_min = [float('inf')] * num_buckets
    bucket_max = [float('-inf')] * num_buckets

    for num in nums:
        idx = (num - min_val) // bucket_size
        bucket_min[idx] = min(bucket_min[idx], num)
        bucket_max[idx] = max(bucket_max[idx], num)

    # Maximum gap is the max of (min of current bucket - max of previous bucket)
    max_gap = 0
    prev_max = min_val

    for i in range(num_buckets):
        if bucket_min[i] == float('inf'):
            continue  # empty bucket
        max_gap = max(max_gap, bucket_min[i] - prev_max)
        prev_max = bucket_max[i]

    return max_gap


print(maximum_gap([3, 6, 9, 1]))  # 3
print(maximum_gap([10]))          # 0

---

7. Stability Analysis

Algorithm	Stable?	Why
Counting sort	Yes	Right-to-left output preserves order
Radix sort (LSD)	Yes	Uses stable counting sort at each digit
Radix sort (MSD)	Yes*	*If stable subroutine is used per bucket
Bucket sort	Depends	Stable if subroutine sort is stable

Stability matters when sorting by multiple keys. Radix sort depends on stability — if the digit-level sort were not stable, LSD radix sort would not work.

---

8. Comparison of Non-Comparison Sorts

Algorithm	Time	Space	Stable	Best For
Counting Sort	O(n + k)	O(n + k)	Yes	Small range integers
Radix Sort (LSD)	O(d(n + b))	O(n + b)	Yes	Fixed-length integers/strings
Radix Sort (MSD)	O(d(n + b))	O(n + b)	Yes	Variable-length strings
Bucket Sort	O(n + k) avg	O(n + k)	Depends	Uniform distribution

Where:

• k = range of values (counting sort) or number of buckets
• d = number of digits
• b = base (10 for decimal, 256 for characters)

---

9. Hybrid Sorting Approach

In practice, you combine these techniques:

def smart_sort(arr):
    """
    Choose the best sort based on data characteristics.
    """
    if not arr:
        return []

    n = len(arr)

    if n <= 50:
        # Small array: insertion sort
        result = arr[:]
        for i in range(1, len(result)):
            key = result[i]
            j = i - 1
            while j >= 0 and result[j] > key:
                result[j + 1] = result[j]
                j -= 1
            result[j + 1] = key
        return result

    min_val, max_val = min(arr), max(arr)
    value_range = max_val - min_val

    if value_range <= 2 * n:
        # Small range: counting sort
        return counting_sort_with_negatives(arr)

    max_digits = len(str(max(abs(min_val), abs(max_val))))
    if max_digits <= 10 and min_val >= 0:
        # Moderate number of digits: radix sort
        return radix_sort_lsd(arr)

    # Default: Python's built-in Timsort
    return sorted(arr)


# Test with different data
print(smart_sort([4, 2, 2, 8, 3, 3, 1]))        # counting sort path
print(smart_sort([170, 45, 75, 90, 802, 24, 2]))  # radix sort path
print(smart_sort([3, 1, 4]))                       # insertion sort path

---

10. Common Interview Applications

Sort by Frequency

def sort_by_frequency(arr):
    """Sort elements by frequency (most frequent first)."""
    from collections import Counter
    freq = Counter(arr)
    max_freq = max(freq.values())

    # Counting sort by frequency
    buckets = [[] for _ in range(max_freq + 1)]
    for num, f in freq.items():
        buckets[f].append(num)

    result = []
    for f in range(max_freq, 0, -1):
        for num in sorted(buckets[f]):
            result.extend([num] * f)

    return result


print(sort_by_frequency([1, 1, 2, 2, 2, 3]))
# [2, 2, 2, 1, 1, 3]

Sort Colors (Dutch National Flag via Counting)

def sort_colors(nums):
    """
    LeetCode 75: Sort Colors.
    Only 3 values (0, 1, 2) — counting sort is perfect.
    """
    count = [0, 0, 0]
    for num in nums:
        count[num] += 1

    idx = 0
    for color in range(3):
        for _ in range(count[color]):
            nums[idx] = color
            idx += 1


colors = [2, 0, 2, 1, 1, 0]
sort_colors(colors)
print(colors)  # [0, 0, 1, 1, 2, 2]

---

11. Practice Problems

Problem	Platform	Key Technique
Sort Colors (LC 75)	LeetCode	Counting sort / DNF
Maximum Gap (LC 164)	LeetCode	Bucket sort
Sort an Array (LC 912)	LeetCode	Radix sort
H-Index (LC 274)	LeetCode	Counting sort
Top K Frequent Elements (LC 347)	LeetCode	Bucket sort by frequency
Sort Characters By Frequency (LC 451)	LeetCode	Counting + bucket
Relative Sort Array (LC 1122)	LeetCode	Counting sort variant
Kth Largest Element (LC 215)	LeetCode	Counting sort on range

---

Big-O Summary

Algorithm	Time	Space	Constraint
Counting sort	O(n + k)	O(k)	k = value range
Radix sort (LSD)	O(d(n + b))	O(n + b)	d = digits, b = base
Radix sort (MSD)	O(d(n + b))	O(n + b + d)	recursive stack
Bucket sort (avg)	O(n + k)	O(n + k)	uniform distribution
Bucket sort (worst)	O(n^2)	O(n + k)	all in one bucket

Non-comparison sorts are not always faster than O(n log n) sorts — they just shift the complexity from comparisons to the structure of the data. When that structure exists (small range, fixed-width keys, uniform distribution), these algorithms are unbeatable.