Поразрядная сортировка

Поразрядная сортировка (англ. radix sort) — алгоритм сортировки, который выполняется за линейное время. Существуют стабильные варианты.

Поразрядная сортировка
Автор	Герман Холлерит
Предназначение	Алгоритм сортировки
Структура данных	Массив
Худшее время	${\displaystyle O(w\cdot n)}$, где w — количество бит, требуемых для хранения каждого ключа.
Затраты памяти	${\displaystyle O(w+n)}$
Медиафайлы на Викискладе

Исходно предназначен для сортировки целых чисел, записанных цифрами. Но так как в памяти компьютеров любая информация записывается целыми числами, алгоритм пригоден для сортировки любых объектов, запись которых можно поделить на «разряды», содержащие сравнимые значения, например, строки, и вообще любые данные, представленные в виде набора байтов.

Сравнение производится поразрядно: сначала сравниваются значения одного крайнего разряда, и элементы группируются по результатам этого сравнения, затем сравниваются значения следующего разряда, соседнего, и элементы либо упорядочиваются по результатам сравнения значений этого разряда внутри образованных на предыдущем проходе групп, либо переупорядочиваются в целом, но сохраняя относительный порядок, достигнутый при предыдущей сортировке. Затем аналогично делается для следующего разряда, и так до конца.

Так как выравнивать сравниваемые записи относительно друг друга можно в разную сторону, на практике существуют два варианта этой сортировки. Для чисел они называются в терминах значимости разрядов числа, и получается так: можно выровнять записи чисел в сторону менее значащих цифр (по правой стороне, в сторону единиц — LSD от англ. least significant digit) или более значащих цифр (по левой стороне, со стороны более значащих разрядов — MSD от most significant digit).

При LSD-сортировке получается порядок, уместный для чисел. Например: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. То есть, здесь значения сначала сортируются по единицам, затем сортируются по десяткам, сохраняя отсортированность по единицам внутри десятков, затем по сотням, сохраняя отсортированность по десяткам и единицам внутри сотен, и так далее.

При MSD-сортировке получается алфавитный порядок, который уместен для сортировки строк текста. Например «b, c, d, e, f, g, h, i, j, ba» отсортируется как «b, ba, c, d, e, f, g, h, i, j». Если MSD применить к числам, то получится алфавитный, но не числовой порядок: 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Накапливать при каждом проходе сведения о группах можно разными способами — например в списках, в дер��вьях, в массивах, выписывая в них либо сами элементы, либо их индексы.

Существует нестабильный вариант рекурсивной побитовой сортировки, выполняющейся непосредственно в сортируемом массиве: на первом проходе движение идёт навстречу друг другу, в начале массива ищется элемент с 1 в первом битовом разряде, в конце массива ищется элемент с 0 в том же разряде. Найденные элементы меняются местами, и так до тех пор, пока рассматриваемые индексы не встретятся. Таким образом в начале массива, до места встречи индексов, собираются все элементы с битом равным 0, а после этого индекса — все элементы с равным 1. Далее рекурсивно можно полностью аналогично перебрать получившиеся поддиапазоны массива, сравнивая значения второго и последующих разрядов, и переставляя элементы местами.