Здесь всё принципиально от дополнительной памяти зависит. Например алгоритм красно-чёрного дерева позволяет добавлять в сортированное дерево новый элемент (оставляя его сортированным) за O(log(N)) операций. Откуда получим уже сложность O(n*log(N)).
Также есть алгоритм работающий за O(M) операций (M — количество возможных значений в диапазоне значений), но при условии, что диапазон значений ограничен:
1) Присваиваем каждой сущности из диапазона своё число от 1 до M в порядке возрастания
2) Создаём массив из M значений
3) Записываем в этот массив по индексу, равному соответствующему сущности числу (на случай коллизий можно, например, списки по индексу хранить — так как порядок одинаковых значений не важен)
Особенно хорошо работает с короткими диапазонами и большим количеством элементов.
Если сортируются числа — ещё удобнее (вместо списков можно количество записывать)
Здесь всё принципиально от дополнительной памяти зависит. Например алгоритм красно-чёрного дерева позволяет добавлять в сортированное дерево новый элемент (оставляя его сортированным) за O(log(N)) операций. Откуда получим уже сложность O(n*log(N)).
Также есть алгоритм работающий за O(M) операций (M — количество возможных значений в диапазоне значений), но при условии, что диапазон значений ограничен:
1) Присваиваем каждой сущности из диапазона своё число от 1 до M в порядке возрастания
2) Создаём массив из M значений
3) Записываем в этот массив по индексу, равному соответствующему сущности числу (на случай коллизий можно, например, списки по индексу хранить — так как порядок одинаковых значений не важен)
Особенно хорошо работает с короткими диапазонами и большим количеством элементов.
Если сортируются числа — ещё удобнее (вместо списков можно количество записывать)