Как работает алгоритм слияния (merge) двух отсортированных массивов?

Алгоритм merge (слияния) объединяет два уже отсортированных массива в один отсортированный массив за линейное время O(n + m), где n и m — длины массивов. Это ключевая часть алгоритма сортировки слиянием (Merge Sort).

Алгоритм (два указателя):

1. Инициализировать указатели i и j в начало первого и второго массивов.
2. Сравнивать элементы arr1[i] и arr2[j].
3. Записывать меньший элемент в результирующий массив и сдвигать соответствующий указатель.
4. Когда один из массивов закончится, скопировать все оставшиеся элементы из другого массива.

Реализация на Python:

def merge_sorted_arrays(arr1, arr2):
    """Сливает два отсортированных списка в один."""
    result = []
    i = j = 0
    # Основной цикл сравнения
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:  # Используем <= для стабильности
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
    # Добавление "хвостов"
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    return result

# Пример использования
print(merge_sorted_arrays([1, 3, 5], [2, 4, 6]))  # [1, 2, 3, 4, 5, 6]

Важные особенности:

• Требует дополнительной памяти O(n + m) для результирующего массива.
• Является стабильным, если при равенстве элементов брать из первого массива.
• В сортировке слиянием алгоритм применяется рекурсивно к подмассивам.