2.6 Mergesort

Übersteigt der Speicherbedarf für die Daten den vorhandenen Rechnerspeicher, müssen die Daten auf mehrere Dateien aufgeteilt werden. Jede einzelne Datei darf nur so groß sein, das sie in den Rechnerspeicher paßt und dort sortiert werden kann. Anschließend werden die einzelnen Dateien wieder zusammengeführt.

1. Lies soviel Daten aus der Datei, wie im Speicher sortiert werden können.
2. Sortiere diese Daten und schreibe sie in eine eigene Datei.
3. Führe die Schritte 1 - 2 solange aus, wie noch Daten vorhanden sind.
4. Lies aus jeder der erzeugten Dateien ein Element.
5. Schreibe das kleinste Element und lies ein neues aus der Datei, aus der das kleinste stammt.
6. Führe die Schritte 4 - 5 solange aus, bis alle sortierten Teildateien ausgelesen sind. Sobald eine dieser Dateien leer ist, wird sie in Schritt 4 und 5 nicht mehr berücksichtigt.

Die Beispiele benutzen nur 2 sortierte Dateien. Der Algorithmus läßt sich auch so implementieren, daß immer nur jeweils 2 Dateien verschmolzen werden. Der Sortieralgorithmus für das Sortieren im Speicher wurde weggelassen. Es kann einer der oben aufgeführten verwendet werden. Aufgrund der großen Datenmenge (sie passen komplett nicht in den Speicher!) sollte ein möglichst schneller gewählt werden.

English version not yet available.