Sąlajos rikiavimo algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
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ą.