1. Последовательность сортируется по старшему значащему двоичному биту так, чтобы все ключи, начинающиеся с 0, оказались перед всеми ключами, начинающимися с 1. Для этого надо найти самый левый ключ Ki, начинающийся с 1, и самый правый ключ Kj, начинающийся с 0, после чего Ri и Rj меняются местами, и процесс повторяется, пока не станет i > j.
2. Пусть F0—множество элементов, начинающихся с 0, а F1—все остальные. Применим к F0 поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество F0 не будет полностью отсортировано; затем проделаем то же с F1.

       Алгоритм  обмена по разрядной сортировки:

       Записи R1, . . . , RN переразмещаются на том  же месте; после завершения сортировки их ключи будут упорядочены:K1 ≤ . . . ≤ KN. Предполагается, что все ключи—m-разрядные двоичные числа (a1 a2 . . . am)2; i-й по старшинству бит ai называется "бит i" ключа. Требуется вспомогательный стек, вмещающий до m − 1 элементов. Этот алгоритм, по существу, следует процедуре обменной поразрядной сортировки с разделениями,

Заключение.

       Казалось  бы, к чему плодить много алгоритмов, давайте найдем один, самый оптимальный  и успокоимся на этом. Это ошибочное  мнение. Найти оптимальный алгоритм, не привязываясь при его выборе к  условию задачи - это иллюзия.

       Какой алгоритм, из множества известных сейчас самый быстрый?

       Ответа  на этот вопрос не существует. Нет самого оптимального алгоритма в абстрактном  смысле. Выбор его очень сильно зависит от условия задачи, которую  необходимо решить.