Recap: Linear-Time Sorting

Three sorts that read keys instead of comparing them, and the assumption each one cannot run without.

Linear-time sorts beat the n log n limit on comparison sorts by using each key's value as an index, and each pays with an assumption about the keys. This card gathers what the topic established and where each idea was taught.

What the topic established, and which card it was on
The idea	Where
Comparison sorts need about log₂(n!) comparisons at worst; reading a key's value escapes that limit	Linear-Time Sorts: Reading the Key Instead of Comparing It
Counting sort counts each value, turns the counts into end positions and places items from the last	Counting Sort: Counting Each Value, Then Placing It
Subtracting the smallest key sizes the count array at max − min + 1 and allows negative keys	Counting Sort in Python, Java and TypeScript
LSD radix sort makes one stable pass per digit, and earlier passes break the ties of later ones	Radix Sort: One Stable Pass per Digit, Least Significant First
A radix pass is a counting pass keyed on value ÷ place mod 10	Radix Sort in Python, Java and TypeScript
Bucket sort is near linear when keys are spread evenly and quadratic when they gather in one bucket	Bucket Sort: Spreading Keys Into Ranges, Then Sorting Each Range
Seven gathered keys cost 13 comparisons in one bucket against 3 for spread keys	Bucket Sort in Python, Java and TypeScript
Counting needs a narrow range, radix fixed-width keys, bucket an even spread	Counting vs Radix vs Bucket Sort
Placing from the first item into end positions reverses equal digits and breaks radix sort	Placing Items Front to Back in a Radix Sort's Counting Pass
Temperatures suit counting sort, 64-bit ids radix sort, and evenly spread readings bucket sort	Practice: Choosing a Sort for Three Sensor Logs

Linear-time sorts on n keys

Counting sort: O(n + k) time, O(n + k) space; k possible key values; every case
Radix sort: O(d · (n + b)) time, O(n + b) space; d digits in base b; every case
Bucket sort, average: O(n + b); keys spread evenly, b about n
Bucket sort, worst case: O(n²); every key in one bucket
Stable: All three; counting placing from the last item; radix and bucket when their inner sorts are stable
In place: None of them; each copies the items into a second array or into buckets

Each of these sorts is faster than any comparison sort on the keys it was built for and useless or slow on the rest, so the skill the topic teaches is reading the keys first. Choosing a Sorting Algorithm, a later topic, sets them beside the comparison sorts and the built-in sorts each language provides.

← → move through sections and cards