mr_virtusответ - возможно для массивов некоторых типов.
А каких конкретно типов не указано? Логический (true/false) можно, но на практике нафиг не нужно.

Поискал, почитал. Корман - это вышеупомянутая блочная сортировка 17305846 . Распихиваем по блокам в один проход, сортировку внутри блока игнорируем как незначительную, получаем сложность O(N). ИМХУ обычный маркенговый бред из серии "Соль пищевая без ГМО".

ZyK_BotaNДа нет, зная внутреннюю структуру данных, и характеристику значений, иногда действительно можно свести сортировку к сложности o(n). и соль без ГМО здесь не причем.
Не согласен. Вот пример реализации из вики

"вставить A[i] в конец массива" не дает никаких шансов использовать тайные знания структуры данных. Если данные попадающие в один блок изначально не стоят в отсортированном порядке, то и в блоке они останутся несортированными.

Т.е. вместо одного массива из N элементов за один проход получили M несортированных массивов. Далее сортируем каждый обычной сортировкой с минимальной сложностью O(n log(n)), т.е. в итоге сортировали все элементы, уже O(n) никак не получается.

Знания структуры данных нужно для предсказания диапазонов, чтобы в каждый блок попало примерно одинаковое количество элементов, т.е. заранее надо знать минимум, максимум и какое-то стат.распределение. Авторы алгоритма успешно "порешали" эту непростую задачу формулировкой " При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке [0, 1) " Упомянули бы алгоритм как привести данные к равномерному распределению в один проход, т.е. вычислить диапазоны для разбиения на примерно равные блоки. Далее исходя из этого же утверждения вывели сложность O(n). Чем не маркетинг?