Linear-Time Sorting

Counting sort, radix sort and bucket sort place each item by reading its key's value instead of comparing it with other items, which lets them sort in time proportional to n on the inputs they suit and leaves them slow or unusable on the rest. The topic opens on the family map, with the limit on comparison sorts that the three get round and the assumption each one makes. Each member then has a concept card and a code card in three languages, all on the same seven keys: counting sort with its count array and end positions, LSD radix sort with one stable counting pass per digit, and bucket sort with its spread and gathered runs. A comparison card sets the three side by side, a gotcha shows a radix sort broken by placing items in the wrong order, and an exercise picks a sort for three sensor logs from their keys alone.