Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35
Narozdíl od vnitřního třídění máme data v souboru (z historických důvodů se říká na pásce, prý), nemáme přímý přístup. Všechny probírané algoritmy využívají slučování/slévaní (angl. merge).
Jako operace se bere čtení a zápis (narozdíl od vnitřního třídění).
(alias Dvoufázové dvoucestné přímé slučování)
Mějme posloupnost, rozdělme ji na dvě posloupnosti, sestávající ze setříděných posloupností délky 1. Slučme tyto setříděné posloupnosti. Atd. Na celé setřídění je třeba log N rozdělení a sloučení. Každé sloučení i rozdělení sestává z N čtení + N zápisů,
Nehodí se pro vnitřní třídění. Potřebuje dvojnásobek paměti než Heap Sort (stejná složitost).
*Složitost:* O(N logN)