Counting vs Radix vs Bucket Sort

Counting sort, radix sort and bucket sort all place items by reading their keys instead of comparing them, all need a second array, and all are stable when written as the code cards write them; they differ in what they need the keys to be. This card puts the same input through all three and gives the rule for choosing among them, or for choosing a comparison sort instead.

The input is 13 4 10 7 14 3 10, sorted by the listings in Counting Sort in Python, Java and TypeScript and the two cards after it. The Time column names each sort's cost and the work each run did on these seven keys.

On seven small keys the three did about the same amount of work, and any of them would do. They part company as the keys change. Widen the range to all 32-bit integers and counting sort needs four billion counters, while radix sort in base 256 still makes four passes of 256 counters each. Gather the keys at one end of the range and bucket sort's buckets empty out except one, as the gathered run on Bucket Sort in Python, Java and TypeScript showed, while counting sort does not care how the keys are spread. Give the keys no digits to read, such as names compared by a locale's rules or records compared by several fields, and none of the three applies.

The rule follows from the Needs column. Use counting sort when the keys are integers in a range no wider than a small multiple of n. Use radix sort when the keys are integers or fixed-length strings whose range is too wide for counting sort. Use bucket sort when the keys are spread evenly over a known range, and especially when they are not integers. Use a comparison sort, usually the built-in one, when the keys fit none of those, when n is small enough that the difference does not matter, or when you cannot be sure the assumption holds, because a comparison sort has no input that breaks it.