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

[p80286]

hallo K6n,

da gibt es was für Dich, ich glaube es heißt mergesort. Ggf. müßtest Du unter externe Sortierverfahren suchen.
Das Prinzip stammt noch aus der Großrechnerzeit.

Im Prinzip funktioniert das in zwei Schritten:
A) lese Eingabedatei
solange Datensatze sortiert vorliegen in Ausgabedatei schreiben.
wenn nicht mehr sortiert dann neue Ausgabedatei anlegen.
B) lies den ersten Datensatz aus allen Ausgabedateien
vergleiche alle Sätze und schreibe den kleinsten in die Pufferdatei
bis alle Ausgabedateien gelesen sind
verarbeite die Pufferdatei mit A)
wenn nur noch eine Ausgabedatei vorliegt ist alles sortiert.

Wenn Dein Verfahren stabil sein soll dann mußt Du beim Wegschreiben der "kleinsten Sätze" den mit dem kleineren Index bevorzugen.
Du kannst das Verfahren beschleunigen indem Du möglichst große Happen vorsortierst. Dann solltest Du allerdings auch hier ein stabiles Verfahren nutzen, also Finger weg von QuickSort.

In der ursprünglichen Version wird nur mit 2 Ausgabedateien gearbeitet. Dann wird immer hin und her geschaltet wenn die Sortierung unterbrochen wird. Das fördert allerdings die Schreib/Lesetätigkeit auf der Platte.

Ich hoffe das hilft Dir weiter

K-H

(ich bin zu langsam!)