Объединение двух отсортированных массивов

Как объединить два отсортированных массива (n1 и n2 элементов) в один отсортированный массив? Такой вопрос мне неоднократно попадался на собеседованиях и даже пару раз сталкивался с ним на практике. Вся сложность этого вопроса не в том как это сделать, а как это сделать максимально быстро.

Быстрее всего это делается за n1+n2 итераций (линейное время). Пусть есть два отсортированных по возрастанию массива A1 и A2. Можно легко определить первый элемент результирующего массива - им будет либо первый элемент первого массива, либо первый элемент второго массива, в зависимости от того, что меньше. Допустим, наименьший - это A1[0]. На следующей итерации при помощи одного сравнения определяется второй элемент результирующего массива - опять сравниваются первые элементы исходных массивов, при условии, что для A1 первый элемент - это A1[1], так как A1[0] - уже выбыл из игры. И так продолжается пока не будет заполнен результирующий массив. На картинке это выглядит так:


Как видно, ничего сложного в этом алгоритме нет. Самое интересное в нем - это возможность использования для сортировки. Любой массив размера n можно представить в виде n массивов, состоящих из одного элемента. Пары соседних элементов, представленных ввиде массивов можно объединять по описанному выше алгоритму. Получится примерно в 2 раза (примерно, потому что n может быть как четным так и нечетным числом) меньше отсортированных массива по 2 элемента, которые в свою очередь тоже можно объединить. И так пока не получится один отсортированный массив.
А все это называется сортировка слиянием.