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

[ThomasNds]

Hallo,

die Google-Stichworte, die du suchst, lauten "externes sortieren"
und "Mischsortieren direktes Mischen". Eine sehr schöne Beschreibung des
Sortierens von DAteien, die nicht in den Hauptspeicher passen,
findet sich in Wirth: Algorithmen und Datenstrukturen. Die englische
Version des Buches gibt es hier (ab Seite 67):
http://www-old.oberon.ethz.ch/WirthPubl/AD.pdf
Einen groben Überblick (ohne Code) liefert z.B.
http://www.inf.fu-berlin.de/lehre/SS...ipt/ALP2K2.pdf

Eine Alternative wäre das Einlesen der Strings in einen B-Baum
oder eine Datenbank, um sie dann sortiert herauszulesen.

Andere Alternative, wenn der Hauptspeicher nur geringfügig
zu klein ist: Ein Array mit Verweisen in die Datei anlegen, etwa

Code:

  Index: Array of Record
                   Stringstart: Fileoffset
                    Stringlänge: Integer
                  end

Ein Arrayelement benötigt 8 Byte, also kann man in z.B. 20 MB
gut 2 Millionen Feldelemente anlegen. Das Array wird gefüllt,
indem man einmal durch die ganze Datei durchliest. Dann sortiert
man das Array (hepasort o.ä). Anschließend kann man die
Strings sortiert aus der Datei auslesen und in eine neue
schreiben.

Gruß

T.