Что касается слияния на месте в массиве

Я наткнулся на следующий вопрос.

Учитывая массив из n элементов и целое число k, где k < п. Элементы {a ₀... a _k} и {a _{k +1}... a _n} уже отсортированы. Дайте алгоритм для сортировки по времени O (n) и O (1).

Мне кажется, что это не может быть сделано в O (n) времени и O (1) пространстве. Проблема действительно заключается в том, чтобы спросить, как сделать шаг слияния mergesort, но на месте. Если бы это было возможно, не было бы реализовано такое объединение? Я не могу убедить себя, хотя и нуждаюсь в некотором мнении.

Ответ 1

Это, кажется, указывает на то, что это возможно в пространстве O (lg ^ 2 n). Я не вижу, как доказать, что невозможно объединить в постоянном пространстве, но я не вижу, как это сделать.

Изменить: Исследуя ссылки, Knuth Vol 3 - Упражнение 5.5.3 говорит: "Значительно более сложный алгоритм Л. Трабба-Пардо дает наилучший ответ на эту проблему: возможно стабильное слияние в O (n) время и стабильная сортировка в O (n lg n), используя только O (lg n) бит вспомогательной памяти для фиксированного числа индексных переменных.

Подробнее ссылки, которые я не читал. Спасибо за интересную проблему.

Дальнейшее редактирование: В этой статье утверждается, что в статье Хуанга и Лангстона есть алгоритм, который объединяет два списка размером m и n во времени O (m + n), поэтому ответ на ваш вопрос кажется да. К сожалению, у меня нет доступа к этой статье, поэтому я должен доверять информации второй руки. Я не уверен, как примирить это с выражением Кнута о том, что алгоритм Трабба-Пардо является оптимальным. Если бы моя жизнь зависела от этого, я бы пошел с Кнутом.

Теперь я вижу, что это было спрошено как и раньше, Qaru question a номер раз. У меня нет сердца, чтобы обозначить его как дубликат.

Хуан Б.-C. и Лангстон М. А., Практическое слияние на месте, Comm. ACM 31 (1988) 348-352

Ответ 2

Есть несколько алгоритмов для этого, ни один из которых очень легко интуитивно. Основная идея состоит в том, чтобы использовать часть массивов для объединения в качестве буфера, а затем выполнить стандартное слияние с использованием этого буфера для вспомогательного пространства. Если вы затем можете переместить элементы так, чтобы элементы буфера находились в нужном месте, вы стали золотыми.

Я написал реализацию одного из этих алгоритмов на моем личном сайте, если вам интересно посмотреть на него. Он основан на статье "Практическое объединение на месте" Хуанга и Лангстона. Вероятно, вам захочется просмотреть эту статью для некоторой проницательности.

Я также слышал, что для этого есть хорошие адаптивные алгоритмы, в которых используется выбранный вами буфер фиксированного размера (который может быть O (1), если вы хотите), но затем элегантно масштабируйте размер буфера. Я не знаю ни одного из них с моей головы, но я уверен, что быстрый поиск "адаптивного слияния" может что-то изменить.

Ответ 3

Нет, это невозможно, хотя моя работа была бы намного проще, если бы это было:).

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

Вот ход слияния и сортировки с 1-9. Обратите внимание, как вам требуется учет в журнальном пространстве для отслеживания инверсий порядка, вызванных двойными ограничениями постоянного пространства и линейных свопов.

Есть некоторые тонкие граничные условия, немного сложнее, чем бинарный поиск, чтобы получить право, и даже в этой (возможной) форме и, следовательно, проблема плохой домашней работы; но действительно хорошие умственные упражнения.

Обновление Видимо, я ошибаюсь, и есть алгоритм, который обеспечивает O (n) время и O (1) пространство. Я загрузил документы, чтобы просветить себя, и отозвать этот ответ как неверный.