Externer Speicher Mergesort

Question

Kann jemand Punkt mich auf eine gute Referenz auf externen Speicher Mergesort? Ich habe die Wiki-Seite lesen, aber Probleme habe es genau zu verstehen. Eine Animation könnte helfen, aber ich kann nicht scheinen, einen zu finden.

Im Grunde weiß ich, dass Sie eine bestimmte Anzahl von Blöcken auf der Festplatte haben, und Sie können eine bestimmte Anzahl von Blöcken in dem Speicher passen. Können sagen, Sie im Speicher 32 Blöcke auf der Festplatte und 4 Blöcke haben. Im ersten Durchgang lesen Sie 4 Blöcke in den Speicher zu einer Zeit, sie sortieren in Erinnerung, und schreiben Sie sie aus den hinteren Scheiben tun. Deshalb an dieser Stelle haben Sie 8 sortierten Läufe von 4 Blöcken. Wie funktioniert die Zusammenführung der Arbeit? Da ich 4 Blöcke im Speicher haben (nehme ich für die Ausgabe eines mehr haben) Ich glaube, sollte ich in der Lage sein, eine Zeit zu fusionieren 4 dieser 8 läuft an, und dann die nächsten 4 läuft fusionieren. Und dann in der letzten passiere ich das Ganze zusammenführen möchten. Aber glauben Sie nicht jeden Block von der Festplatte jedes Mal gelesen haben? Wie funktioniert dies nicht eine n ^ 2 Lösung werden?

Answer 1

Ich glaube, ich es bekommen. Beim Zusammenführen Sie noch alle Blöcke auf der Festplatte lesen (nennen wir, dass B), aber Sie haben sie nicht mal B zu lesen. Sie sie B log B mal gelesen.