BLOK 08 · 2 godz. Sortowanie O(n log n) Dziel i zwyciężaj

MergeSort — sortowanie przez scalanie

Informatyka Rozszerzona · Klasa 4 · Semestr I · Blok 08/30

1. Idea sortowania przez scalanie

MergeSort to klasyczny algorytm typu "dziel i zwyciężaj": dzielimy tablicę na połowy, rekurencyjnie sortujemy każdą połowę, a następnie scalamy (merge) dwie posortowane połowy w jedną posortowaną całość. Kluczowa obserwacja: scalenie dwóch posortowanych tablic można wykonać w czasie liniowym.

2. Implementacja

def merge_sort(tab):
    if len(tab) <= 1:
        return tab
    srodek = len(tab) // 2
    lewa = merge_sort(tab[:srodek])
    prawa = merge_sort(tab[srodek:])
    return scal(lewa, prawa)

def scal(lewa, prawa):
    wynik = []
    i = j = 0
    while i < len(lewa) and j < len(prawa):
        if lewa[i] <= prawa[j]:
            wynik.append(lewa[i]); i += 1
        else:
            wynik.append(prawa[j]); j += 1
    wynik.extend(lewa[i:])
    wynik.extend(prawa[j:])
    return wynik

3. Wizualizacja podziału i scalania

[8, 3, 5, 1, 9, 2] → dzielimy na [8, 3, 5] i [1, 9, 2]

[8, 3, 5] → [8] i [3, 5] → [3, 5] → [3] i [5] → scal → [3, 5]

scal([8], [3, 5]) → [3, 5, 8]

[1, 9, 2] → analogicznie → [1, 2, 9]

scal([3, 5, 8], [1, 2, 9]) → [1, 2, 3, 5, 8, 9]

4. Analiza złożoności

Przypadek	Złożoność czasowa	Uzasadnienie
Najgorszy / średni / najlepszy	O(n log n)	log n poziomów podziału × O(n) na scalenie każdego poziomu
Pamięć	O(n)	Potrzebna dodatkowa tablica pomocnicza do scalania

Stabilność

MergeSort jest algorytmem stabilnym — elementy o równych kluczach zachowują względną kolejność z tablicy wejściowej. To ważne np. przy sortowaniu rekordów według wielu kryteriów.

5. Ćwiczenia praktyczne

Ćwiczenie 1 — policz liczbę inwersji

Zmodyfikuj MergeSort tak, aby przy okazji zliczył liczbę inwersji w tablicy, czyli par (i, j) takich, że i < j, ale tab[i] > tab[j]. Wskazówka: liczba inwersji przyrasta w funkcji scal, gdy element z prawej tablicy trafia do wyniku przed elementem z lewej.

Ćwiczenie 2 — sortowanie rekordów

Mając listę słowników reprezentujących uczniów (imię, średnia_ocen), posortuj ją malejąco według średniej ocen za pomocą MergeSort, dostosowując warunek porównania w funkcji scal.

Sprawdź wiedzę

1. Jaka jest złożoność czasowa MergeSort w każdym przypadku?

O(n²) O(n log n) O(n)

2. Ile dodatkowej pamięci wymaga MergeSort?

O(1) O(log n) O(n)

3. Czy MergeSort jest algorytmem stabilnym?

Tak Nie Zależy od implementacji scal

Podsumowanie bloku

Rozumiem podział problemu sortowania na mniejsze podproblemy w MergeSort.
Potrafię zaimplementować funkcję scalącą dwie posortowane tablice w czasie liniowym.
Rozumiem, dlaczego złożoność MergeSort wynosi O(n log n) w każdym przypadku.
Wiem, co oznacza stabilność algorytmu sortującego i dlaczego ma znaczenie.

← Blok 07: Grafy Blok 09: QuickSort i Counting Sort →