INF.04Algorytmika i Struktury Danych
Sortowanie przez scalanie (Merge Sort)
Stabilny algorytm sortowania dzielący tablicę na połowy, sortujący je rekurencyjnie i scalający dwa posortowane ciągi w czasie O(n log n).
Zasada działania Merge Sort:
- Dziel: Podziel tablicę n-elementową na dwie równe podtablice o rozmiarze n/2.
- Zwyciężaj: Rekurencyjnie posortuj obie podtablice.
- Połącz (Scal): Scal dwie posortowane podtablice w jedną posortowaną całość w czasie liniowym O(n).
Cechy algorytmu:
- Złożoność czasowa: Gwarantowane O(n log n) w każdym przypadku (optymistycznym, średnim i pesymistycznym).
- Złożoność pamięciowa: O(n) – wymaga pomocniczej tablicy o rozmiarze danych wejściowych.
- Stabilność: Algorytm stabilny.
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Sortowanie przez scalanie (Merge Sort) lub rozpocznij trening.