(Вначале стоит просто спросить про мерж, потом добавить про память и время.)
Ну и да, придумать полный вариант за время интервью нереально, но если расслабить констрейнты - тогда всё хорошо. Т.е. это скорее personality test, нежели coding test.
UPD: Пример входных данных:
6 (длина), 7 (длина), 10, 11, 12, 100, 101, 102, 1, 2, 3, 4, 200, 210, 220 (13 байт данных)
This entry was originally posted at http://wizzard.dreamwidth.org/418797.html. It has
Взять второй массив, читать с конца, сравнивать с концом первого, если больше - свапнуть, и так до головы, получили сортнутый хвост, проверили что начальный элемент меньше конечного во втором, иначе повторили с элемента второго массива который меньше хвоста в первом (хвост не до конца сортнут),
потом первый массив побили по первому неравенству соседних элементов и тем же алгоритмом.