Ферлонам, Хаустовым Павлам и сочувствующим -- можно ниже не читать :о)
Для остальных -- отличная задача.
Дан массив длины 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.
Почти любое наивное решение не способно решить один из них.