Sąlajinis rikiavimas

Algoritmas
Tipas	Rikiavimo algoritmai
Pavadinimas	Sąlajos (Merge sort)
Sudėtingumas	Vidutinis - N·log(N)); blogiausias - N·log(N)
Greitos nuorodos	Algoritmai Rikiavimo algoritmai Sąlajos Šablonas

Sąlajinis rikiavimas^[1] (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ą.

Sąlajos rikiavimo algoritmas yra „skaldyk ir valdyk“ metodikos algoritmas, kurį išrado Džonas fon Noimanas 1945 m.^[2]

Šaltiniai

↑ sąlajinis rikiavimas. V. Dagienė, G. Grigas, T. Jevsikova. Enciklopedinis kompiuterijos žodynas. 4-as leidimas. Vilnius: VU MII, 2014 // EKŽ, 2021, nuolat atnaujinamas. ISBN 978-9986-680-52-9.
↑ Knuth, Donald (1998). „Section 5.2.4: Sorting by Merging“. Sorting and Searching. The Art of Computer Programming. 3 (2nd leid.). Addison-Wesley. p. 158. ISBN 0-201-89685-0.

[1] sąlajinis rikiavimas. V. Dagienė, G. Grigas, T. Jevsikova. Enciklopedinis kompiuterijos žodynas. 4-as leidimas. Vilnius: VU MII, 2014 // EKŽ, 2021, nuolat atnaujinamas. ISBN 978-9986-680-52-9.

[2] Knuth, Donald (1998). „Section 5.2.4: Sorting by Merging“. Sorting and Searching. The Art of Computer Programming. 3 (2nd leid.). Addison-Wesley. p. 158. ISBN 0-201-89685-0.

[1]