Цифровая распределяющая сортировка основана на наблюдении, что если имена уже отсортированы по младшим разрядами
, то их можно полностью отсортировать, сортируя только по старшим разрядам
при условии, что сортировка осуществляется таким образом, чтобы не нарушить относительный порядок имен с одинаковыми цифрами в старших разрядах. Заметим, что к самой таблице обращаются по правилу "первым включается – первым исключается", и поэтому лучшим способом представления являются очереди. В частности, предположим, что с каждым ключом
ассоциируется поле связи
; тогда эти поля связи можно использовать для сцепления всех имен в таблице вместе во входную очередь
. При помощи полей связи можно также сцеплять имена в очереди
, используемые для представления стопок. После того как имена распределены по стопкам, очереди, представляющие эти стопки, связываются вместе для получения вновь таблицы
. Алгоритм 15.4. представляет эту процедуру в общих чертах (очереди описаны в лекции 11). В результате применения алгоритма очередь
будет содержать имена в порядке возрастания; то есть имена будут связаны в порядке возрастания полями связи, начиная с головы очереди
