Сортировка «Американский флаг»

[dmrt]

Это был тяжелый год,
Был он тяжелей, чем тот

[a5b]

Подскажите, где в Кнуте TAOCP описаны эти и подобные вариации radix sort?
(American flag sort… is an efficient, in-place variant of radix sort)

[valemak]

Кнут не очень углублялся в поразрядные сортировки. В третьем томе в главе 5.2.2 всего 5 страниц уделяется поразрядному способу. Там у него поразрядная сортировка по младшим разрядам. Сортировка «Американский флаг» сортирует по старшим разрядам, так что дополнительной информации к этой статье у Кнута Вы не найдёте :-)