Urejanje z zlivanjem
Urejanje z zlivanjem (angleško MergeSort) je stabilen algoritem za urejanje podatkov, ki ga je leta 1945 razvil John von Neumann.
| Urejanje z zlivanjem | |
|---|---|
 Grafični prikaz urejanja z zlivanjem | |
| Osnovni podatki | |
| Vrsta: | algoritem za urejanje podatkov |
| Podatkovna struktura: | tabela |
| Časovna zahtevnost | |
| Zgornja meja zahtevnosti: | O(n log n) |
| Spodnja meja zahtevnosti: | O(n log n) |
| Pričakovana zahtevnost: | O(n log n) |
| Prostorska zahtevnost | |
| Prostorska zahtevnost: | O(n) |
Delovanje uredi
Algoritem uporablja paradigmo deli in vladaj. Začne s podtabelami velikosti 1, ki so same po sebi seveda urejene. Nato začne z zlivanjem(in sprotnim urejanjem) parov podtabel v večjo podtabelo in te tabele nato zopet zliva v večje, dokler ne zlije vseh elementov tabele v eno urejeno tabelo.
Zahtevnost uredi
Časovna zahtevnost je v vseh primerih , prostorska zahtevnost pa je , saj za podtabele potrebujemo dodaten prostor. Algoritem je možno implementirati tudi s prostorsko zahtevnostjo , a pri tem izgubimo stabilnost algortima.
