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

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

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

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

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

Теперь я вижу, что этот вопрос был задан как и ранее Stack Overflow вопрос a количество раз. У меня нет духа отмечать это как дубликат.

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

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

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

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

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

У вас есть фактор 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). Я скачал документы, чтобы просветить себя, и беру этот ответ как неверный.