Слияние сортировки: работа алгоритма, пример и реализация на Python

30 Дней Алгоритмов: С Нуля до Уверенного Пользователя - 8. Слияние сортировки

Чем мы займемся?

В сегодняшнем руководстве мы рассмотрим алгоритм слияния сортировки, популярный алгоритм сортировки, который относится к так называемым алгоритмам "разделяй и властвуй". Мы рассмотрим:

• Как работает слияние сортировки
• Пошаговый пример
• Псевдокод и реализация на Python

Как работает слияние сортировки?

Алгоритм слияния сортировки работает путем рекурсивного деления исходного списка на более мелкие части, пока каждый элемент не будет представлять собой список из одного элемента. Затем эти списки объединяются обратно вместе в отсортированном порядке.

Вот подробное объяснение шагов слияние сортировки:

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

Пошаговый пример

Рассмотрим следующий список в качестве примера:

[5, 3, 1, 2, 4]

Разделение:

• Сначала мы разделяем список пополам на [5, 3] и [1, 2, 4].
• Затем мы снова разделяем [5, 3] на [5] и [3].
• Наконец, мы разделяем [1, 2, 4] на [1], [2] и [4].

Завоевание:

• Каждый из этих списков содержит только один элемент, поэтому они уже отсортированы.

Слияние:

• Сначала мы объединяем [5] и [3] в [3, 5].
• Затем мы объединяем [3, 5] и [1] в [1, 3, 5].
• Далее мы объединяем [1, 3, 5] и [2] в [1, 2, 3, 5].
• Наконец, мы объединяем [1, 2, 3, 5] и [4] в [1, 2, 3, 4, 5].

Псевдокод и реализация на Python

Псевдокод:

def merge_sort(arr):
    if len(arr)