Sorting Algorithms Part 3: Linear-Time Sorting, Counting, Radix, and Bucket

1. Introduction. The hook of today

In Part 2 we reached n log n time with divide and conquer. Today we go even further. When the data satisfies certain numeric assumptions, we can sort in time that is linear in the number of elements. The key is to stop comparing pairs and instead use structure in the input space.

We will cover three classics:

• Counting Sort, a frequency based method that places values directly.
• Radix Sort, a digit by digit method that uses a stable inner routine.
• Bucket Sort, a distribution method for real values that are spread roughly uniformly.

As always, you can experiment with every algorithm in the Sorting Algorithms Playground.

2. Why linear sorts are possible

Comparison sorts must make enough decisions to distinguish among n factorial permutations, which leads to a lower bound of n * log n comparisons.
Linear sorts avoid pairwise comparisons and instead map values to positions by arithmetic.
This works when keys fall in a limited integer range, or when numbers have a bounded number of digits, or when real values are distributed well across an interval.

---

3. Counting Sort

3.1 Properties

Time: O(n + k)
Space: O(n + k)
Stable: yes
In place: no

3.2 Intuition

We count how many times each value appears, then we transform counts into cumulative counts so that each value knows where its block ends in the output.
By scanning the input from right to left we place elements into their final positions and preserve the relative order of equals, which makes the algorithm stable.

3.3 Implementation

def counting_sort(arr):
    if not arr:
        return []

    min_val, max_val = min(arr), max(arr)
    k = max_val - min_val + 1
    count = [0] * k

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

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

    output = [0] * len(arr)

    for i in range(len(arr)-1, -1, -1):
        count[arr[i]-min_val] -= 1
        output[count[arr[i]-min_val]] = arr[i]

    return output

3.4 Notes and trade offs

This version handles any contiguous integer range by shifting indices by the minimum value.
It is stable because we insert elements from right to left.

Space grows with the value range, so it is best when the range k is of the same order as n.

---

4. Radix Sort

4.1 Properties

Time: O(d × (n + b)), where d is the number of digits and b is the base
Space: O(n + b)
Stable: yes when the inner pass is stable
In place: no

4.2 Intuition

Sort by the least significant digit first, then by the next digit, and so on.
If each digit pass is stable, the ordering created by earlier passes is preserved.
For signed integers we split into negative and non negative groups, sort magnitudes, then merge with the negatives reversed.

4.3 Implementation

def radix_sort(nums, base=10):
    if len(nums) <= 1:
        return nums[:]

    non_neg = [x for x in nums if x >= 0]
    neg = [-x for x in nums if x < 0]

    def lsd(nums):
        if not nums:
            return nums

        max_v = max(nums)
        exp = 1
        out = [0] * len(nums)

        while max_v // exp > 0:
            count = [0] * base

            for num in nums:
                digit = (num // exp) % base
                count[digit] += 1

            for idx in range(1, base):
                count[idx] += count[idx-1]

            for i in range(len(nums)-1, -1, -1):
                digit = (nums[i] // exp) % base
                count[digit] -= 1
                out[count[digit]] = nums[i]

            exp *= base
            nums, out = out, nums

        return nums

    ordered_neg = lsd(neg)
    neg_again = [-x for x in reversed(ordered_neg)]

    ordered_non_neg = lsd(non_neg)

    return neg_again + ordered_non_neg

4.4 Notes and trade offs

The inner pass is a stable counting sort on a single digit.

Work is proportional to the number of digits times the array length, plus the base.
This is excellent when the number of digits is small, for example fixed width integers.

---

5. Bucket Sort

5.1 Properties

Time: O(n + k) on uniform data, worst case can degrade to quadratic when data clusters
Space: O(n + k)
Stable: yes when intra bucket sorts are stable
In place: no in the usual form

5.2 Intuition

Divide the numeric interval into k buckets.
Place each value into its bucket according to a mapping function.
Sort each bucket, often with insertion sort for small buckets, then concatenate the buckets in order.
When values are spread uniformly the buckets remain small and total work is linear.

5.3 Implementation

def bucket_sort(arr, bucket_count=10):
    if not arr:
        return []

    buckets = [[] for _ in range(bucket_count)]

    for x in arr:
        # ensure the last value falls into the last bucket
        idx = min(bucket_count - 1, int(x * bucket_count))
        buckets[idx].append(x)

    for b in buckets:
        b.sort()

    out = []
    for b in buckets:
        out.extend(b)
    return out

5.4 Notes and trade offs

The mapping from value to bucket index is the heart of the method.
If the data range is not [0, 1), apply an affine transform or adapt the index function.
When distribution is even, each bucket holds about n over k items and the total work is near linear.
When many values fall into one bucket the method slows down to the cost of the bucket sort, which is often n squared for insertion sort.

---

6. Comparing the three

Counting Sort: O(n + k), integer keys from a bounded range, stable, extra memory proportional to the range.
Radix Sort: O(d × (n + b)), works by digits, relies on stability, ideal for fixed width integers.
Bucket Sort: O(n + k) on uniform data, depends on a good bucket mapping, natural for real values in a known interval.

---

7. Quick comprehension check

Questions

1. Why do linear sorts not violate the n log n lower bound for comparison sorts?
2. When would you choose Counting Sort over Radix Sort?
3. What is the role of stability in Radix Sort?

Answers

1. Because they do not perform pairwise comparisons to order elements, they use arithmetic indexing or digit passes instead.
2. When the integer range is small relative to n and you need a single stable pass without digit logic.
3. It preserves the order created by earlier digit passes so that after the final pass the global order is correct.

---

8. Final summary and review

Linear sorting works by replacing comparisons with direct placement.
Counting Sort uses cumulative counts to compute positions.
Radix Sort applies a stable pass per digit and supports negatives by splitting and recombining.
Bucket Sort distributes values into subranges and sorts locally.
Together with the quadratic and the n log n families, these complete the classic map of sorting techniques.