Сортування злиттям

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
        
# Приклад використання:
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
        print("Відсортований масив:", arr)
        

Ключовий момент на самому початку:

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. Сортуємо кожну частину окремо

Такий підхід дуже сильно прискорює алгоритм.