Работая над примером кода для вопроса об алгоритме, я столкнулся с ситуацией, когда я сортировал входной массив, хотя мне нужно было только сгруппировать идентичные элементы, но не в каком-то определенном порядке, например:

{1,2,4,1,4,3,2} → {1,1,2,2,4,4,3} или {1,1,2,2,3,4,4} или {3 , 1,1,2,2,4,4} или ...

Что заставило меня задуматься:Можно ли сгруппировать идентичные элементы в массив более эффективно, чем путем сортировки массива?

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

Логичным кандидатом будет типсортировка, но что, если длина массива и / или диапазон значений будут нереально большими?

В качестве аргумента, скажем, массив большой (например, миллион элементов), содержит 32-разрядные целые числа, и число идентичных элементов на значение может быть любым от 1 до миллиона.

ОБНОВЛЕНИЕ: Для языков с поддержкой словарей, ответ Сальвадора Дали, очевидно, путь. Мне все еще было бы интересно услышать о старомодных методах сравнения и обмена или методах, которые занимают меньше места, если таковые имеются.