Относительно слияния на месте в массиве

Question

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

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

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

Answer 1

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

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

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

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

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

Хуан Б.-С. и Langston M.A., Практическое объединение на месте, Comm. ACM 31 (1988) 348-352

Answer 2

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

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

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

Answer 3

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

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