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

Question

Нашел следующий вопрос.

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

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

Answer 1

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

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

Подробнее references10, что я еще не читал. Проблема:

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

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

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

Answer 2

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

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

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

 
.  - 
135792468 
. - 
135792468 
    : .- 
125793468 
    : .- 
123795468 
    #.:- 
123495768 
    :.- 
123459768 
     .:- 
123456798 
     .- 
123456789 

123456789 

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

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

Answer 3

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

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

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