Карманная сортировка для случая повторяющихся ключей

Рассмотренный метод можно обобщить следующим образом. Пусть по-прежнему ключи могут иметь значения только от 1 до n, но во входном наборе каждое значение может повторяться любое число раз, в том числе и ноль. Пусть исходный массив содержит m элементов, причем m>n. В этом случае с одним и тем же ключом может быть связано несколько элементов, и их нельзя поместить в одну ячейку результирующего массива.

Очевидным решением является использование вспомогательных списков для хранения элементов с одинаковыми ключами. Тем самым, приходим к использованию комбинированной структуры данных, а именно – массиву списков. Каждая ячейка массива соответствует одному конкретному значению ключа в диапазоне от 1 до n и хранит указатель на связанный список одноключевых элементов.

Тогда прежде всего надо распределить элементы входного набора по ячейкам результирующего массива в соответствии со значениями ключей, создавая и дополняя при необходимости вспомогательные списки. После этого, если требуется получить общий результирующий отсортированный набор данных, можно объединить все списки, добавляя в конец одного списка начало другого. Это легко реализуется, если в каждой ячейке результирующего массива хранить не только адрес первого элемента списка, но и адрес последнего элемента.

Пример. Пусть задан следующий входной набор из 15 элементов с диапазоном изменения ключей от 1 до 5 (в скобках указан ключ элемента):

а₁(4), а₂(2), а₃(5), а₄(1), а₅(4), а₆(3), а₇(4), а₈(3), а₉(5), а₁₀(1), а₁₁(3), а₁₂(2), а₁₃(2), а₁₄(5), а₁₅(3)

Тогда эти элементы будут распределены следующим образом:

ключ	а10 а4 указатели
	начало
а12 а13 а2 конец
	начало
а8 а15 а11 а6 конец
	начало
конец
	а7 а5 а1 начало
конец
	а14 а9 а3 начало
конец

После объединения списков получим:

а₄, а₁₀, а₂, а₁₂, а₁₃, а₆, а₈, а₁₁, а₁₅, а₁, а₅, а₇, а₃, а₉, а₁₄

Для программной реализации необходимо объявить массив указателей и ссылочный тип для поддержки списков. Дополнительные затраты памяти связаны в первую очередь с реализацией дополнительных списков, т.к. общее число элементов в этих списках равно m, а кроме того для каждого элемента надо 4 байта для адресных полей. Трудоемкость данного метода оценивается соотношением O(m+n), а при m>>n становится пропорциональной числу элементов m.