Große Datei sortieren ohne komplett in den Speicher zu laden

[nahpets]

Hallo,

Zitat von k6n:

Die gängigen Sortierverfahren sind mir bekannt, aber die benötigen immer ein komplettes Array mit den Werten und um das zu bekommen, muss man die Datei komplett in den Speicher laden und genau das möchte ich ja nicht.

na schön, der MergeSort, der dort beschrieben ist, dürfte (ggfls. nach Aufarbeitung) ja genau Dein Problem lösen. Der MergeSort im Beispielquelltext arbeitet halt mit zwei Teilen, das sieht aber so aus, als könne man mit etwas Aufwand da auch 4 oder 8 oder mehr Teile draus machen. Für das Sortieren der einzelnen Teile musst Du dann immer nur eines der Teile im Speicher haben und sortieren. Das schreibst Du dann temporär weg. Beim Zusammenfügen nimmst Du zuerst Teil 1 und 2, dann Teil 1 und 3 ...
Na, zum Mergen könnte man dann auch die einzelnen Teile parallel von der Platte lesen und in eine neue Datei schreiben, man liest die einzelnen Teile solange, bis der aktuelle Satz einer anderen Datei kleiner als der eigene ist. Das kann man über (fast) beliebig viele Dateien machen. Der Programmieraufwand dürfte nicht mal übermäßig groß sein.

Wie groß sind die zu sortierenden Dateien den überhaupt?