Ř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.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- ano
- ne
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ě
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.