Реализация сортировки с объединением, не используя дополнительный массив?
Я недавно читал много о сортировке с объединением, и интересно, существует ли способ сделать сортировку с объединением, не используя по крайней мере один дополнительный массив. Действительно ли это возможно?
3 ответа
Согласно Wikipedia Википедия Это действительно возможно, но может не дать какую-либо усиление производительности:
возможна сортировка на месте (например, использование списков, а не массивов), но очень сложно, и будет Предложите небольшую производительность на практике, даже если алгоритм работает в O ( n log N ). В этих случаях алгоритмы, такие как Heapsort, обычно предлагают сопоставимую скорость и намного менее комплекс. Кроме того, в отличие от стандартной сортировки слияния, сортировка слияния на месте не является стабильным сортировкой. В случае связанных списков алгоритм не использует больше пространства, чем то, что уже используется представлением списка, но o (log ( k )), используемый для следа рекурсиона. Некоторые утверждают, что сортировка связанного списка не на месте, потому что даже если вы сортируете в данной структуре данных, структура данных по своей природе имеет O ( n ) дополнительных данных, которые вы управляете (например, ссылки в список).
Видимо, так и есть. В данной работе описывается вид локального слияния:
детально проанализированы два локальных варианта классического алгоритма слияния. Первый, прямолинейный вариант выполняет максимум в N logе сравнения 2 N + O(N ), а 3N log 2 N + O(N ) переходит к сортировке N элементов. Второй, более продвинутый вариант требует в максимум N лог 2 сравнений N + O(N ) и "N лог 2 N перемещается, для любого фиксированного " ? 0 и любой N ? N ("). Теоретически, второй вариант превосходит продвинутые версии heapsort. На практике, из-за накладных расходов при манипуляции с индексами, наш самый быстрый на месте слияния ведет себя примерно на 50% медленнее, чем восходящий хеппорт. Однако наши реализации практичны по сравнению с алгоритмами слияния, основанными на слиянии на месте.
Юрки Катаяйнен, Томи Пасанен, Юкка Тейухола, "Практическое внутреннее слияние" (1996).
Нет, вам всегда понадобится дополнительная структура данных, чтобы объединить отсортированные элементы. Если нет, то вы просто перезапишите то, что уже отсортировано.