M = 3 (s použitím externího třídění)

• M = 3 (s použitím externího třídění)

•  ~ 2pR log(pR) + 2pS log(pS) + pR + pS bez zápisu výsledku

• M  pS (dvoufázový algoritmus)

• (1) Vytvářejí se setříděné běhy velikosti 2M stránek (pomocí prioritní fronty) a ukládají na disk;

• •  velikost běhu je  2pS
  •  pro S jich je nejvýše pS/2pS,pro R také ne více než pS/2pS
  •  celkem nejvýše pS

• (2) Pro každý běh se alokuje v paměti stránka a souběžně se slévá;

•  3(pR + pS) bez zápisu výsledku