Слияние массивов

У нас есть два отсортированных массива (например, два списка чисел), и нужно получить новый, тоже отсортированный, в котором будут все элементы из обоих массивов.

На первый взгляд можно просто «склеить» массивы и отсортировать результат:

A = [1, 4, 7]
B = [2, 3, 6, 8]
C = sorted(A + B)
print(C)  # [1, 2, 3, 4, 6, 7, 8]

Это работает, но неэффективно:

• склейка (A+B) — линейная операция O(n),
• сортировка — квадратичная (O(n²)), если использовать только простые алгоритмы, которые мы изучали.

Итого: O(n²) — слишком дорого.

Идея алгоритма «Слияние»

Можно сделать лучше: всего за O(n). Для этого используем два указателя (маркера), которые будут двигаться по массивам. Пусть есть два массива:

A = [1, 4, 7]
B = [2, 3, 6, 8]

Заводим два маркера: i = 0 для массива A и j = 0 для массива B.

Сравниваем A[i] и B[j].

• Меньший из элементов переносим в результат C.
• Передвигаем соответствующий маркер на один шаг вперёд.

Повторяем, пока не закончится один из массивов. Остаток второго массива дописываем целиком в C.

def merge_sorted_lists(A, B):
    """Слияние двух отсортированных списков"""
    i, j = 0, 0
    C = []
    
    while i < len(A) and j < len(B):
        if A[i] < B[j]:
            C.append(A[i])
            i += 1
        else:
            C.append(B[j])
            j += 1
    
    # Добавляем остатки
    C.extend(A[i:])
    C.extend(B[j:])
    
    return C

# Пример
A = [1, 4, 7]
B = [2, 3, 6, 8]
print(merge_sorted_lists(A, B))  # [1, 2, 3, 4, 6, 7, 8]

Сложность алгоритма

• Каждый элемент мы сравниваем и переносим ровно один раз.
• Если в массивах n и m элементов, то итоговая сложность:

O(n+m) — линейная.

Это оптимальный результат

Реализация на NumPy

import numpy as np

def merge_numpy(A, B):
    """Слияние двух отсортированных numpy.array"""
    i, j = 0, 0
    C = []
    
    while i < len(A) and j < len(B):
        if A[i] < B[j]:
            C.append(A[i])
            i += 1
        else:
            C.append(B[j])
            j += 1
    
    # Остатки
    C.extend(A[i:])
    C.extend(B[j:])
    
    return np.array(C)

# Пример
A = np.array([1, 4, 7])
B = np.array([2, 3, 6, 8])
print(merge_numpy(A, B))  # [1 2 3 4 6 7 8]