Слияние двух упорядоченных массивов разными подходами

Условие

Даны два отсортированных массива, необходимо получить один объединённый массив, сохранив порядок элементов. Предлагается реализовать несколько вариантов решения задачи.

arr_a = [1, 3, 5, 7, 9]
arr_b = [2, 6, 7, 8, 9]

Ответ

Оптимально сливать массивы двумя указателями за O(n+m), каждый раз выбирая меньший текущий элемент. Повторы сохраняются. Альтернативы — sorted(a+b) и ленивый heapq.merge.

Линейное слияние:

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

Для примера получится [1, 2, 3, 5, 6, 7, 7, 8, 9, 9]. sorted(a+b) короче, но не выражает напрямую линейное слияние. list(heapq.merge(a,b)) использует готовый ленивый механизм; оба входа должны быть отсортированы.