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

8.1 Определение сортировки слиянием

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

Принцип работы:

Разделение:

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

Слияние:

• Сливайте два соседних подмассива в один отсортированный массив.
• Повторяйте процесс слияния, пока не будет получен один отсортированный массив.

Временная и пространственная сложность сортировки слиянием

Временная сложность:

• В худшем случае: O(n log n)
• В среднем случае: O(n log n)
• В лучшем случае: O(n log n)

Пространственная сложность:

O(n) — дополнительная память необходима для хранения временных подмассивов.

8.2 Метод нисходящего слияния

Исходная последовательность рекурсивно разбивается на половины, пока не получим подпоследовательности по 1 элементу. Из полученных подпоследовательностей формируем упорядоченные пары методом слияния, затем — упорядоченные четвёрки и так далее.

Рассмотрим последовательность:

Разбиваем последовательность на 2 половины (рекурсивно, пока не получим пары).

Каждую подпоследовательность упорядочиваем методом слияния и получаем готовую последовательность.

8.3 Реализация алгоритма сортировки слиянием

Вот тут нам и пригодится рекурсия! Это очень хороший и быстрый алгоритм по сравнению с предыдущими. Он делит массив пополам, сортирует обе части отдельно, а затем быстро объединяет отсортированные части.

Выглядит его реализация примерно так:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Находим середину массива
        left_half = arr[:mid]  # Делим массив на два подмассива
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Рекурсивно сортируем левую половину
        merge_sort(right_half)  # Рекурсивно сортируем правую половину
        
        i = j = k = 0
        
        # Слияние отсортированных половин
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # Проверка на оставшиеся элементы
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# Пример использования:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Отсортированный массив:", sorted_arr)
# Вывод: Отсортированный массив: [3, 9, 10, 27, 38, 43, 82]

Ключевой момент в самом начале:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 # Находим середину массива
        left_half = arr[:mid] # Делим массив на два подмассива right_half = arr[mid:]
        
        merge_sort(left_half)  # Рекурсивно сортируем левую половину
        merge_sort(right_half)  # Рекурсивно сортируем правую половину

Вот что тут происходит:

1. Мы находим середину массива
2. Делим массив на 2 части
3. Сортируем каждую часть отдельно

Такой подход очень сильно ускоряет алгоритм.

2

Задача

Модуль 1: Python Core, 18 уровень, 7 лекция

Недоступна

Объединение массивов

Объединение массивов

Открыть

2

Задача

Модуль 1: Python Core, 18 уровень, 7 лекция

Недоступна

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

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

Открыть