Memoria esterna merge sort

Question

qualcuno mi può puntare a un buon riferimento su Memory Mergesort esterna? Ho letto la pagina wiki, ma sto avendo difficoltà a capire esattamente. Un aiuto di animazione forza, ma non riesco a trovarne uno.

In sostanza, so che hai un certo numero di blocchi sul disco, e si può montare un certo numero di blocchi in memoria. Diciamo che avere 32 blocchi su disco e 4 blocchi in memoria. Nel primo passaggio si legge 4 blocchi in memoria alla volta, li sorta in memoria, e li scrive di nuovo fuori farlo disco. Quindi a questo punto si dispone di 8 piste selezionate di 4 blocchi. Come funziona il fusione? Poiché ho 4 file di memoria (assumere Ho un altro per l'uscita) Credo dovrebbe essere in grado di unire 4 di tali 8 piste alla volta, e poi unire i prossimi 4 piste. E poi l'ultimo passo che voglio unire il tutto. Ma non si deve leggere ogni blocco dal disco ogni volta? Così come questo si trasformi in un n ^ 2 soluzione?

Answer 1

Credo di aver capito adesso. Quando si uniscono avete ancora leggere tutti i blocchi sul disco (la chiamata di let che B), ma non c'è bisogno di leggerli volte B. Hai letto solo a loro volte di registro B B.