Стабильный, эффективный сорт?

Question

Я пытаюсь создать необычную реализацию ассоциативного массива, которая очень экономит пространство, и мне нужен алгоритм сортировки, который удовлетворяет всем следующим требованиям:

1. Стабильный (не изменяет относительный порядок элементов с равными ключами.)
2. Стек на месте или почти на месте (O (log n) - это нормально, но нет использования O (n) пространства или кучи.
3. O (n log n) сложность времени.

Также обратите внимание, что сортируемая структура данных - это массив.

Легко видеть, что есть базовый алгоритм, который соответствует любым 2 из этих трех (сортировка вставок соответствует 1 и 2, сортировка слиянием соответствует 1 и 3, сортировка кучи соответствует 2 и 3), но я не могу для себя найдите все, что соответствует всем трем критериям.

Answer 1

Не беспокойтесь о O (n log n), пока не продемонстрируете, что это важно. Если вы можете найти алгоритм O (n ^ 2) с радикально меньшей константой, сделайте это!

Общий сценарий наихудшего случая не имеет значения, если ваши данные сильно ограничены.

Короче говоря: запустить тест.

Answer 2

Возможно оболочка сортировки ? Если я правильно помню курс по структурам данных, он имел тенденцию быть стабильным, но в худшем случае O (n log ^ 2 n), хотя он выполняет O (n) почти отсортированных данных. Он основан на сортировке вставкой, поэтому он сортируется на месте.

Answer 3

Может быть, я немного в затруднительном положении, но мне нравится сортировка с ручным кодированием. Это просто, стабильно и хорошо себя ведет. Необходимое дополнительное временное хранилище составляет всего N*sizeof(int), что не так уж и плохо.