Как реализовать слияние двух отсортированных массивов в один отсортированный

Что проверяют

Классическое слияние двумя указателями и понимание, что в Python оно почти всегда уже написано в стандартной библиотеке, а выбор между ручной реализацией и готовой зависит от объёма данных.

Как отвечать

Ручная реализация:

def merge_sorted(a, b):
    res = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:])
    res.extend(b[j:])
    return res

Сравнение <= вместо < делает слияние устойчивым: при равных ключах первым идёт элемент из первой последовательности. Для кортежей и объектов, сравниваемых по одному полю, это наблюдаемое поведение. Хвосты дописываются срезами, отдельные циклы не нужны: срез за границей возвращает пустой список, а не ошибку.

Сложность: O(n+m) по времени и по памяти, каждый элемент читается один раз.

Готовые инструменты и когда какой брать:

• heapq.merge(a, b, key=..., reverse=...) сливает любое число упорядоченных источников и возвращает ленивый итератор. Это правильный выбор для файлов и генераторов: потребление памяти не зависит от объёма данных, что и нужно во внешней сортировке шардов датасета или логов. Сложность O(N log k) по числу источников.
• sorted(a + b) тоже работает и на практике близок к линейному: Timsort обнаруживает две готовые серии и делает по сути одно слияние. Но конкатенация создаёт лишнюю копию, а на итераторах вариант неприменим.
• В numpy своя история: np.concatenate плюс np.sort, а для вставки короткого упорядоченного массива в длинный np.searchsorted даёт позиции за O(m log n).
• В pandas слияние по упорядоченному ключу это pd.merge_asof, и он требует предварительной сортировки: на неотсортированных данных результат будет неверным.

Перед кодом уместно уточнить: нужны ли дубли (если нет, после слияния добавляется проход, схлопывающий равные), помещаются ли данные в память, сколько последовательностей сливаем. При k источниках ручная реализация естественно превращается в кучу.

Где спотыкаются

Пишут while i < len(a) or j < len(b) и получают IndexError; либо сразу предлагают sorted(a + b) как единственный ответ, не показав, что понимают сам алгоритм слияния.