Ферлонам, Хаустовым Павлам и сочувствующим -- можно ниже не читать :о)
Для остальных -- отличная задача.
Дан массив длины 2N. Первые N элементов и последние N элементов отсортированы по возрастанию. Надо отсортировать весь массив за линейное время с константой памяти.
Я предполагаю, что это не классика, потому что существует (неверное) (распространенное) мнение, что лучшая реализация Merge Sort требует O(N) памяти. Сам факт, что описанная выше задача имеет решение, очевидно, опровергает это.
UPD: Ваши решения можно проверить на случаях
6 7 8 9 10 1 2 3 4 5
и
1 3 5 7 9 2 4 6 8 10.
Почти любое наивное решение не способно решить один из них.
Complexity
Linear in comparisons (N-1) if an internal buffer was used, NlogN otherwise (where N is the number elements in the range [first,last)).C++ не гарантирует, что не будет заведено O(n) памяти -- более того, STLPort заводит линейную память в inplace_merge.
Не смотря на то, что ожидаемое значение слова inplace -- это то, что память заведена не будет, в контексте STL это значит всего лишь, что результат будет там же, где были параметры.
Если бы массив состоял из чисел, задача бы решалась radix sort'ом.
Разумеется, никаких допущених по поводу природы элементов, помимо того, что на них определен оператор <, делать нельзя.
После этого массив не будет отсортирован:
1 3 5 7 9 11
2 4 6 8 10 12
Двойка поменяется с тройкой, тройка с пятеркой, после чего мы перейдем ко второму элементу второй половины (к четверке), и пятерка останется на всегда в начале второй половины, в то время как она там оставаться не должна.
сейчас буду вникать более подробно
1 3 2 4
Пусть p1 достиг позиции N, когда p2 был где-то в середине своей половины. Тогда [0,N) отсортирован, [N,p2) отсортирован и [p2,2N) осортирован -- у нас есть три отсортированных массива, как мы их сливаем?
Алгоритм опирается на то, что [0,p1] отсортирован. Я не могу понять, что алгоритм делает пересекая N-ный элемент, чтобы [0,p1) остался отсортирован. Допустим, что p1 указывает на N-1-ый элемент (последний в первой половине), а p2 на некоторый элемент, который больше. Тогда мы сдвигаем p1, и он оказывается на N-ом элементе, который меньше, чем N-1-ый (так как он попал сюда в результате свопа какого-то элемента, который был левее N-1-ого). Значит отсортированность [0,p1] нарушилась.
(даблпост)
Решение этой задачи очень сложное и не практичное (скрытая константа большая).
Доказательство:
Если бы это было не так, то задача была бы классикой и расписана везде где можно (от Кнута до Кормена).
Следствие:
Все решения в этой ветке неправильные, т.к. для описания правильного решения (с доказательством) не хватит лимита символов для комментария :)
Решение действительно не практичное.
Но описать его займет не намного больше, чем любое описанное здесь неправильное решение :о)
> Если бы это было не так, то задача была бы классикой и расписана везде где можно (от Кнута до Кормена).
Ошибочка... Ваше доказательство неверное. См. Кнут, 3-й том, раздел 5.2.4, упражнение №18.
Эта жесть работает в предположении, что мы можем сделать циклический сдвиг массива длины n на k единиц за время O(n) и память O(1). Вроде бы мы так можем делать))
Щас еще поразмыслю и запостчу картинки. Без них вообще ничо не будет понятно:D
UPD. Уже не важно. Обломал.
1(5 6 | 4)(2 3 7 8 9)
1 3 5 7 9 10 2 4 6 8 11 12
1) позиция очередного отсортированного элемента.
2) позиция на очередной элемент второй половины, он будет сдвигаться всегда вправо.
3) позиция на очередной элемент первой половинки (которая инвертирована) и этот указатель будет двигаться влево. А когда будет пытаться выйти левее указателя (1). его будем автоматически передвигать на поицию перед указателем (2)
Ну и процесс обмена будет таков: Очередной минимальный элемент будем обменивать с элементом в позиции (1) (хвост первой половинки). Ну и двигать соответствующий указатель...вроде нигде не ошибся. Возможно для первой половинки еще пригодится хранить количество оставшихся элементов, чтоб было проще с указателями, но все равно памяти O(1)
Примеры работы алгоритма для последовательности Автора:
[] (9 7 5 3 1!) (2! 4 6 8 10)
[1] (7 5 3! 9) (2! 4 6 8 10)
[1 2] (5 3! 9 7) (4! 6 8 10)
[1 2 3] (5! 9 7) (4! 6 8 10)
[1 2 3 4] (9 7 5!) (6! 8 10)
[1 2 3 4 5] (7! 9) (6! 8 10)
[1 2 3 4 5 6] (9 7!) (8! 10)
[1 2 3 4 5 6 7] (9!) (8! 10)
[1 2 3 4 5 6 7 8] (9!) (10!)
[1 2 3 4 5 6 7 8 9] (первая последовательность закончилась длина 0) (!10)
[1 2 3 4 5 6 7 8 9 10]
для входа: 6 7 8 9 10 1 2 3 4 5 все тоже самое, только вторая последовательность закончится быстрее, а первая тупо будет циклически сдвигаться по массиву.
[1] (7 5 2! 9) (3! 4 6 8 10)
[1 2] (5! 7 9) (3! 6 8 10)
ЗЫ: Я правильно понимаю автора, что задача узкозаточненная, правильный алгоритм будет работать тогда и только тогда, когда длина левой половины равна длине правой половины?
Нет, правильное решение работает в случае, когда половины не равны.
В ответах есть решение со ссылочками.
Отмечу, что Кнут считает эту задачу довольно трудной (40 из 50).
У нас его парнишке задали на интервью в одну компанию. Видимо, они очень не хотели, чтобы он прошел :о)
А потом уже решение мы с ним нашли как раз в Кнуте.