Почему мы не можем применить сортировку подсчетом к общим массивам?

Недостаточно знать верхнюю границу, чтобы запустить сортировку подсчетом: вам нужно иметь достаточно памяти, чтобы поместить все счетчики.

Рассмотрим ситуацию, когда вы просматриваете массив 64-битных целых чисел и обнаруживаете, что самый большой элемент равен 2^60. Это будет означать две вещи:

• Вам нужна память O (2 ^ 60) и
• Для завершения сортировки потребуется O (2 ^ 60).

Тот факт, что O(2^60) совпадает с O(1), здесь мало помогает, потому что постоянный множитель просто слишком велик. Это очень часто проблема с алгоритмами псевдополиномиального времени.

Предположим, что самое большое число равно 235684121. Тогда вы потратите невероятное количество оперативной памяти, чтобы хранить свои корзины.

Я хотел бы упомянуть кое-что с ответами @dasblinkenlight и @AlbinSunnanbo, ваша идея сканировать массив в O(n) проходе, чтобы найти максимальное значение в массиве, в порядке. Ниже приводится из Википедии:

Однако, если значение k еще не известно, его можно вычислить с помощью дополнительного цикла по данным, чтобы определить максимальное значение ключа, которое действительно встречается в данных.

Поскольку временная сложность равна O(n + k), а k должна быть ниже определенного предела, найденное k должно быть небольшим. Как упомянул @dasblinkenlight, O(large_value) практически невозможно свести к O(1).

Хотя я до сих пор не знаю ни о каких крупных применениях сортировки подсчетом, кроме использования в качестве подпрограммы сортировки по основанию, ее можно хорошо использовать в таких задачах, как сортировка строк (т.е. сортировать «android» на «addnoir»), так как здесь k всего 255.