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

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

Основные шаги:

1. Разделение: Если массив содержит более одного элемента, он делится на два подмассива примерно равного размера.
2. Рекурсивная сортировка: Сортировка слиянием рекурсивно вызывается для каждой из двух подмассивов.
3. Слияние: Отсортированные подмассивы объединяются (сливаются) в один отсортированный массив.

def merge_sort(arr):
    # Базовый случай: если массив содержит 0 или 1 элемент, он уже отсортирован
    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 = []
    i = 0  # Указатель для левой половины
    j = 0  # Указатель для правой половины

    # Сравниваем элементы из обеих половин и добавляем наименьший в результат
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Добавляем оставшиеся элементы из левой половины (если есть)
    while i < len(left):
        result.append(left[i])
        i += 1

    # Добавляем оставшиеся элементы из правой половины (если есть)
    while j < len(right):
        result.append(right[j])
        j += 1

    return result

# Пример использования
# unsorted_list = [12, 11, 13, 5, 6, 7]
# sorted_list = merge_sort(unsorted_list)
# print(sorted_list) # [5, 6, 7, 11, 12, 13]

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

Преимущества:

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

Недостатки:

• Требует дополнительной памяти O(n) для слияния подмассивов.