Сортировка массива с двумя отсортированными последовательностями в альтернативном положении в линейном времени и постоянном пространстве

Question

Это было задано мне сегодня в одном из интервью, и его выгнали после того, как мы смотрели на вопрос в течение 5 минут.

Учитывая массив A такой, что подпоследовательность всехнечетные позиции ([ A ₁ , A ₃ , A ₅ ,…]) И подпоследовательность всех четных позиций ([ A ₂ , A ₄ , A ₆ ,…]) каждый в отсортированном порядке - например, [1, 7, 2, 8, 3, 9, 4, 10, 5] или [3, 8, 4, 11, 5] или[5, 2, 7, 4] - сортировка A в O ( n ) времени и O (1) пространства (включая пространство стека и пространство выходного массива).

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

Как мы можем решить это?Все входные данные приветствуются.

Answer 1

Если (1) две чередующиеся последовательности могут образовывать одну монотонную последовательность при отсутствии чередования, и либо (а) массив начинается с наименьшего числа и имеет нечетную длину, либо (б) Массив начинается с наименьшего номера второй последовательности (той, которая будет справа, когда не перемежается) и имеет четную длину, мы можем изменить алгоритм, описанный в . Алгоритм размещения для In-Shuffle (Пейюш Джайн, 2008) .

Сначала мы должны выполнить последовательности «лидер цикла», а затем смены цикла.

Пример 1

[1, 7, 2, 8, 3, 9, 4, 10, 5]
 1  2  3  4  5  6  7   8  9
 1  6  2  7  3  8  4   9  5

|1| unaffected

   |1     3                |
   m = 4; 2m = 3^2 - 1
   cycles start on 3^0, 3^1
   (4 swaps with 7 and the other
    numbers form a longer cycle.)

Пример 2 (простой):

[1, 5, 2, 7, 3]
 1  2  3  4  5
 1  4  2  5  3

|1| unaffected

   |          |
   m = 1
   cycle in 2m => 2, 5
   cycle in 2m => 3, 7
   cycle shift by m between 5 and 3
   => 2, 3, 5, 7

Я бы не ожидал, что кто-то придет с этим в интервью, не получив разрешения на исследования:)