Sąlajos rikiavimo algoritmas
|
Šiam straipsniui ar jo daliai trūksta išnašų į šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais. |
| Algoritmas | |
| Tipas | Rikiavimo algoritmai |
| Pavadinimas | Sąlajos (Merge sort) |
| Sudėtingumas | Vidutinis - N·log(N)); blogiausias - N·log(N) |
| Greitos nuorodos | |
Sąlajos rikiavimas (angl. mergesort) – vienas iš „skaldyk ir valdyk“ paradigma besiremiančių rikiavimo algoritmų. Jo principas – skaidyti duomenis į dvi dalis, kiekvieną dalį atskirai surikiuota ir po to sulieti, taikant šį principą rekursyviai. Šio algoritmo realizacijos dažniausiai naudoja pagalbinę atmintį.
Algoritmo efektyvumas nepriklauso nuo duomenų, stabilus, sudėtingumas – O(N·logN), papildomos atminties tūris proporcingas duomenų kiekiui. Galima algoritmą derinti su kitais rikiavimo algoritmais, taip pagerinant efektyvumą.