4. Поразрядная («карманная») сортировка
 

Рассмотренные выше методы обеспечивали сортировку на месте, без использования дополнительной памяти для размещения сортируемых массивов. Имеются также методы сортировки, использующие дополнительные массивы. К ним относятся методы поразрядной сортировки и методы сортировки слиянием.

Алгоритмы поразрядной сортировки рассматривают ключи сортируемых элементов как числа с основанием R и работают с отдельными цифрами чисел. При побайтовом рассмотрении ключей, если ключами являются десятичные числа, то R = 10, при сим-ольных ключах R = 128 или R = 256. При побитовом рассмотрении ключей R = 2.

Алгоритм поразрядной сортировки заключается в том, что при очередном проходе элементы исходного массива помещаются в R массивов (раскладываются по R «карманам») в зависимости от значения младшей цифры ключа. При R = 10, ключи начинающиеся с 0, окажутся в первом массиве, начинающие с 1, — во втором массиве и т.д., т.е. потребуется 10 дополнительных массивов «карманов». Далее данные, находящиеся в каждом «кармане», раскладываются по значениям второй цифры и т.д., пока не будут рассмотрены все цифры ключей. Очевидно, что сколько бы проходов ни сделали, общее число сортируемых элементов остается постоянным, а «карманы» будут содержать разное количество элементов. Поэтому одного дополнительного массива того же размера, что и исходный, было бы достаточно, и в нем можно было бы разместить все «карманы». Однако размеры «карманов» определяются только в процессе очередного прохода, поэтом, видимо, наиболее подходящим способом реализации «карманов» будет применение цепных списков, а не массива.