Ферлонам, Хаустовым Павлам и сочувствующим -- можно ниже не читать :о)

Для остальных -- отличная задача.

Дан массив длины 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.

Почти любое наивное решение не способно решить один из них.