Counting, bucket and radix sort

Counting sort, bucket sort and radix sort put values in order without ever comparing two of them, which lets them beat the n log n cost of comparison sorts when the values are small integers or keys of fixed width. Counting sort counts how often each value occurs and rebuilds the list from the counts, in O(n + k) time for values from 0 to k. Bucket sort spreads values over ranges of equal width and deals with each range on its own. Radix sort orders fixed-width keys digit by digit, with one stable counting pass per digit, last digit first. This lesson’s problem needs the sorted order of a large log only at its widest gap, and asks for it in linear time.

The problem: the longest quiet spell

1. [3600, 120, 900, 7200, 1500] gives 3600. In order the times are 120, 900, 1500, 3600 and 7200, and the last two are furthest apart.
2. [500, 500, 500] gives 0: three parcels in the same second.
3. [86399, 0] gives 86399.

The brute force, and why sorting is not allowed

For every scan, look through all the scans for the next later time, and keep the largest difference. That is exactly n² steps: 4,000,000 for 2,000 scans and 10¹² for a million. Sorting first and comparing neighbours is fast in practice, but it breaks the stated limit, and the run shows why no comparison sort can meet it:

# The longest quiet spell by brute force: for each scan, look through every scan for the next later time.
# Then the cost of the usual fix, sorting first, and the least any comparison sort can do.
import math
import random


def longest_gap_brute(times):
    """Returns the largest gap between consecutive times in sorted order, and the steps taken: exactly n * n."""
    steps = 0
    best = 0
    for t in times:
        following = None  # the smallest time later than t
        for u in times:
            steps += 1
            if u > t and (following is None or u < following):
                following = u
        if following is not None:
            best = max(best, following - t)
    return best, steps


for times in ([3600, 120, 900, 7200, 1500], [500, 500, 500], [86399, 0]):
    print(times, "->", longest_gap_brute(times)[0])

rng = random.Random(3)
for n in (1_000, 2_000):
    _, steps = longest_gap_brute([rng.randint(0, 10**9) for _ in range(n)])
    print(f"n = {n:,}: {steps:,} steps")
print(f"n = 1,000,000: {10**12:,} steps")


class Counted:
    """A time that counts how often sorted() compares it with another (sorted() only uses <)."""
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.comparisons += 1
        return self.value < other.value


sorted(Counted(rng.randint(0, 10**9)) for _ in range(100_000))
print(f"sorting 100,000 times: {Counted.comparisons:,} comparisons")
bound = math.ceil(math.lgamma(1_000_001) / math.log(2))
print(f"any comparison sort, 1,000,000 distinct times: at least {bound:,} comparisons on its worst input")

[3600, 120, 900, 7200, 1500] -> 3600
[500, 500, 500] -> 0
[86399, 0] -> 86399
n = 1,000: 1,000,000 steps
n = 2,000: 4,000,000 steps
n = 1,000,000: 1,000,000,000,000 steps
sorting 100,000 times: 1,532,014 comparisons
any comparison sort, 1,000,000 distinct times: at least 18,488,885 comparisons on its worst input

Python’s sort compared 1,532,014 pairs for 100,000 times, close to n log₂ n. That is no quirk of one library. A sort that only compares must tell apart all n! orders of n different values, and each comparison has two outcomes, so some input needs at least log₂ n! comparisons: 18,488,885 for a million times. Linear time means not comparing the times with each other at all.

What to notice

The times are integers in a known range, so a time can serve as an address, the way counting sort uses each value. And the widest gap is never narrower than the average gap: the n − 1 gaps between neighbours add up to the largest time minus the smallest, so at least one of them is that wide. Two times that are closer together than the average gap can never be the two ends of the answer.

Buckets narrower than the average gap Pro: opens with a Pro, Premium or Ultimate pass