Řazení slučováním

Rozdělí seznam na poloviny, každou polovinu seřadí a pak obě poloviny sloučí do jednoho seřazeného seznamu.

nejlepší Ω(n log n)
průměrný Θ(n log n)
nejhorší O(n log n)
paměť O(n)
stabilní
potřebuje paměť navíc

Co to znamená?

Nejlepší případ: jak roste čas s velikostí seznamu n, když je vstup pro tento algoritmus nejsnazší.
Průměrný: obvyklý růst času s n. Při n² trvá dvakrát víc hodnot asi čtyřikrát déle; n log n roste mnohem pomaleji.
Nejhorší: růst času na nejtěžším vstupu. Důležitý, když se řazení nesmí nikdy zpomalit.
Paměť: kolik paměti navíc je potřeba kromě seznamu. 1 znamená pár proměnných, n kopii seznamu.
Stabilní: dvě stejné hodnoty si zachovají původní pořadí. Důležité při řazení záznamů podle jednoho pole.
Bez paměti navíc: řadí přímo uvnitř seznamu, bez druhého seznamu.

porovnávání
přesun
na konečném místě

0 / 263 kroků

Porovnání Zápisy

Stiskněte Přehrát: čáry ukazují, jak během řazení rostou náklady

Rychlost 8 kroků/s

Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.

Zkuste: Zvolte seznam s málo různými hodnotami. Ze dvou stejných hodnot se nejdřív vezme ta z levé poloviny, takže stejné hodnoty drží pořadí.

Jak to funguje

Dělte seznam, dokud v každém kousku nezůstane jediná hodnota. Takový kousek je už seřazený. Pak kousky slučujte po dvojicích: porovnejte první hodnoty obou kousků a vezměte menší, znovu a znovu. Zvednutá řada v animaci je paměť navíc, kterou slučování potřebuje.

Kdy se hodí

Když potřebujete rychlost, která vydrží i v nejhorším případě, a stejné hodnoty si musí zachovat pořadí. Python i Java používají jednu z verzí řazení slučováním. Nevýhodou je paměť navíc, kterou potřebuje.