Merge sort

O(n log n)

Merge sort je metoda rozděl a panuj: pole půlí až na jednotlivé prvky a pak sousední seřazené úseky slévá zpět do pořadí. Jádrem je slévání — dva už seřazené úseky se v lineárním čase proplétají do jednoho. Garantuje O(n log n) ve všech případech a je stabilní, za cenu pomocné paměti při slévání.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Rozděl pole na dvě poloviny a každou seřaď stejným způsobem (rekurze).
  2. Slij obě seřazené poloviny: opakovaně ber menší z čelních prvků.
  3. Zapiš seřazený úsek zpět přes původní rozsah.
  4. Postupuj nahoru, dokud není celé pole jeden seřazený úsek.

Pseudokód

1mergeSort(a, lo, hi):               # O(n log n)2  if lo ≥ hi: return3  mid ← (lo + hi) / 24  mergeSort(a, lo, mid)5  mergeSort(a, mid+1, hi)6  merge(a, lo, mid, hi)             # weave two sorted halves