Sortowanie przez scalanie (Merge Sort)

1. Idea algorytmu

Merge Sort to klasyczny algorytm "dziel i zwyciężaj" (divide and conquer):

  1. Dziel: Podziel listę na dwie połowy
  2. Zwyciężaj: Rekurencyjnie posortuj obie połowy
  3. Scalaj: Scal dwie posortowane połowy w jedną

Wizualizacja:

[38, 27, 43, 3, 9, 82, 10]
         ↓ DZIEL
    /              \
[38, 27, 43, 3]  [9, 82, 10]
     ↓ DZIEL         ↓ DZIEL
  /       \        /      \
[38, 27] [43, 3] [9, 82] [10]
  ↓        ↓       ↓       ↓
[38][27] [43][3] [9][82] [10]
  ↓        ↓       ↓       ↓
[27, 38] [3, 43] [9, 82] [10]  ← SCALANIE
     ↓              ↓
[3, 27, 38, 43]  [9, 10, 82]   ← SCALANIE
         ↓
[3, 9, 10, 27, 38, 43, 82]     ← KONIEC!

2. Implementacja podstawowa

3. Wizualizacja z debugiem

Wynik:

DZIEL: [38, 27, 43, 3]
  DZIEL: [38, 27]
    DZIEL: [38]
    ← Zwracam: [38] (bazowy)
    DZIEL: [27]
    ← Zwracam: [27] (bazowy)
  SCALANIE: [38] + [27] = [27, 38]
  DZIEL: [43, 3]
    DZIEL: [43]
    ← Zwracam: [43] (bazowy)
    DZIEL: [3]
    ← Zwracam: [3] (bazowy)
  SCALANIE: [43] + [3] = [3, 43]
SCALANIE: [27, 38] + [3, 43] = [3, 27, 38, 43]

4. Scalanie krok po kroku

Przykład: merge([3, 27], [10, 38])

left  = [3, 27]      i = 0
right = [10, 38]     j = 0
result = []

Krok 1: left[0]=3 <= right[0]=10  → result = [3], i=1
Krok 2: left[1]=27 > right[0]=10  → result = [3, 10], j=1
Krok 3: left[1]=27 <= right[1]=38 → result = [3, 10, 27], i=2
Krok 4: i >= len(left) → result.extend(right[1:]) = [3, 10, 27, 38]

Wynik: [3, 10, 27, 38]

5. Złożoność czasowa: O(n log n) ✅

Analiza:

Wysokość drzewa rekurencji = log₂(n)

Każdy poziom przetwarza wszystkie n elementów (scalanie)

Razem: n × log(n) = O(n log n)

Wszystkie przypadki: O(n log n)!

  • Najlepszy: O(n log n)
  • Średni: O(n log n)
  • Najgorszy: O(n log n)

Gwarantowana wydajność – zawsze O(n log n)!

6. Złożoność pamięciowa: O(n)

Merge sort NIE jest in-place (wymaga O(n) pamięci).

7. Stabilność: TAK ✅

Merge sort jest stabilny – zachowuje kolejność równych elementów.

Dlaczego?

Warunek <= sprawia, że elementy z lewej listy (wcześniejsze) mają priorytet.

Przykład:

8. Implementacja in-place (zaawansowana)

Standardowy merge sort używa O(n) pamięci. Można zrobić in-place, ale jest to znacznie bardziej skomplikowane:

Uwaga: Nadal wymaga O(n) pamięci tymczasowej!

9. Wariant: Bottom-up Merge Sort (iteracyjny)

Zamiast rekurencji – sortuj "od dołu":

Zalety: - Brak rekurencji (oszczędność stosu) - Lepsza kontrola nad pamięcią

10. Porównanie: Top-down vs Bottom-up

Aspekt Top-down (rekurencja) Bottom-up (iteracja)
Prostota ✅ Prostsza Bardziej złożona
Pamięć stosu O(log n) O(1) ✅
Wydajność Podobna Podobna
Łatwość zrozumienia ✅ Łatwiejsza Trudniejsza

W praktyce: Top-down (rekurencja) jest popularniejszy.

11. Sortowanie połączonych list

Merge sort jest idealny dla list połączonych (linked lists):

Zalety dla linked lists: - Nie wymaga dodatkowej pamięci O(n) (tylko O(1))! - Naturalnie pasuje do struktury

12. Zastosowania praktyczne

12.1. Sortowanie dużych plików (External Merge Sort)

Gdy dane nie mieszczą się w pamięci:

12.2. Zliczanie inwersji

13. Benchmark

Przykładowe wyniki:

n= 1000: Merge=0.0068s, Python=0.0003s
n= 5000: Merge=0.0412s, Python=0.0018s
n=10000: Merge=0.0891s, Python=0.0037s

Wniosek: Python's Timsort (hybrydowy z merge sort) jest szybszy!

14. Podsumowanie

Merge Sort:

  • Złożoność czasowa: O(n log n) ZAWSZE ✅
  • Złożoność pamięciowa: O(n) (out-of-place)
  • Stabilny: TAK ✅
  • Adaptywny: NIE (zawsze O(n log n))

Zalety: - Gwarantowana wydajność O(n log n) - Stabilny (zachowuje kolejność równych) - Przewidywalny (zawsze ten sam czas) - Idealny dla list połączonych (O(1) pamięci!) - Parallelizable (łatwy do zrównoleglenia)

Wady: - Wymaga O(n) dodatkowej pamięci - Nie adaptywny (zawsze O(n log n), nawet dla posortowanych) - Wolniejszy od quick sort średnio

vs Quick Sort: - Merge: gwarantowane O(n log n), Quick: średnio O(n log n) - Merge: stabilny, Quick: niestabilny - Merge: O(n) pamięci, Quick: O(log n) pamięci - Quick: szybszy średnio

vs Heap Sort: - Merge: stabilny, Heap: niestabilny - Merge: O(n) pamięci, Heap: O(1) pamięci ✅ - Merge: szybszy w praktyce

Kiedy używać:

✅ Gdy potrzebujesz gwarantowanej wydajności O(n log n) ✅ Gdy stabilność jest wymagana ✅ Sortowanie list połączonych ✅ External sorting (duże pliki) ✅ Parallel sorting (łatwe do zrównoleglenia)

❌ Gdy masz ograniczoną pamięć (użyj heap sort) ❌ Gdy chcesz średnio najszybszego (użyj quick sort)

Zastosowania w praktyce:

  1. Timsort (Python) – hybrydowy z merge sort
  2. Java Arrays.sort() – dla obiektów (stabilność)
  3. External sorting – sortowanie dużych plików
  4. Parallel sorting – łatwy do zrównoleglenia

Co dalej warto poznać:

  • Quick Sort (praktyczny wybór)
  • Timsort (hybrydowy algorytm Pythona)
  • External Merge Sort (dla dużych danych)
  • Parallel Merge Sort
Wróć do spisu lekcji