Что такое сортировка слиянием?

Сортировка слиянием (Merge Sort) — это алгоритм сортировки, основанный на принципе "разделяй и властвуй". Он рекурсивно разбивает массив на меньшие подмассивы до тех пор, пока не останутся подмассивы из одного элемента (которые считаются отсортированными). Затем он постепенно сливает эти отсортированные подмассивы, создавая отсортированный массив большего размера.

Алгоритм состоит из двух основных этапов:

1. Разделение: Массив рекурсивно делится пополам до тех пор, пока каждый подмассив не будет содержать только один элемент.
2. Слияние: Отсортированные подмассивы сливаются попарно, создавая новые отсортированные подмассивы большего размера. Этот процесс продолжается до тех пор, пока все подмассивы не будут объединены в один отсортированный массив.

Функция слияния принимает два отсортированных подмассива и объединяет их в один отсортированный массив. Это делается путем сравнения первых элементов каждого подмассива и добавления наименьшего из них в результирующий массив, пока оба подмассива не станут пустыми.

Сортировка слиянием является стабильной (сохраняет относительный порядок равных элементов) и имеет гарантированное время выполнения О(n log n) как в худшем, так и в среднем и лучшем случаях. Однако она требует дополнительной памяти О(n) для временного хранения при слиянии.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # Разделение массива пополам
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Рекурсивная сортировка подмассивов
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # Слияние отсортированных подмассивов
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    left_index = 0
    right_index = 0

    # Сливаем элементы в отсортированном порядке
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

    # Добавляем оставшиеся элементы, если таковые есть
    result.extend(left[left_index:])
    result.extend(right[right_index:])

    return result

# Пример использования
# unsorted_array = [38, 27, 43, 3, 9, 82, 10]
# sorted_array = merge_sort(unsorted_array)
# print(sorted_array)