Überblick:
Dies ist ein Modul mit generischen Prozeduren zur schnellen Sortierung
von beliebigen Datentypen. 
Dabei wurden zwei Algorithmen implementiert und zwar Heapsort und
Quicksort.
Heapsort wurde 1964 von J. Williams entwickelt und zeichnet sich
durch gute Sortierzeiten in allen Lagen aus. Der Algorithmus garantiert
für den schlechtesten, den mittleren und den besten Fall jeweils eine
Laufzeit von O ( n log n ), d.h. bei Vergrößerung der Datenmenge, 
auf n beträgt die Laufzeitkomplexität ( nur um eine Konstante beschränkt ) 
n * log ( n ).
Quicksort wurde 1962 von C. Hoare entwickelt und hat die bisher beste
bekannte Laufzeit im mittleren Fall. Leider kann der Algorithmus entarten,
wenn bei der Teilung der Sortierbereiche immer ein falsches Vergleichs-
element genommen wird. Dann wird Quicksort zum "Slowsort" mit der
Laufzeit O ( n ^ 2 ). Das kommt aber so gut wie nie vor. Weil Quicksort 
in der Praxis ca. zwei mal schneller ist, ist es in den meisten Fällen 
Heapsort vorzuziehen.

Anwendung:
Die Prozeduren haben beide dieselben Prozedurparameter:

VAR a         : ARRAY OF BYTE;
    comp      : CompareProc;
    copy      : CopyProc;
    anz, size : LONGINT )

In a muß ein ARRAY [ 0 .. anz - 1 ] OF Ingentwas übergeben werden.
Z.B. ARRAY [ 0 .. 10 ] OF INTEGER
Die untere Arraygrenze muß aber 0 sein!

Mit comp wird eine Vergleichsprozedur übergeben, die zwei Irgentwas
vergleicht. Diese Prozedur muß folgendermaßen deklariert sein:

   CompareProc = PROCEDURE ( ADDRESS,
                             ADDRESS ) : INTEGER;
   (* Braucht zwei Zeiger auf die zu vergleichenden Elemente.
      Gibt einen Integer zurück: 
      falls beide Element gleich:                       = 0,
      falls erstes Element kleiner als zweites Element: < 0,
      sonst:                                            > 0. *)

Häufig gebrauchte Vergleichsprozeduren sind:
RETURN Integer1 - Integer2;
RETURN Compare ( String1, String2 );
Konkrete Beispiele für Integer- und Stringvergleiche 
siehe Programme SortLibTest.mod und SimpleSort.

Mit copy wird eine Kopierprozedur übergeben, die ein Irgentwas in ein 
anderes kopiert. Diese Prozedur muß folgendermaßen deklariert sein:

   CopyProc    = PROCEDURE ( ADDRESS,
                             ADDRESS );
   (* 
      Braucht zwei Zeiger auf die zu kopierenden Elemente. 
      Copiert das zweite Element in den Speicherbereich des 
      ersten Elements.
   *)

Häufig gebrauchte Kopierprozeduren sind:
Integer1 := Integer2;
Copy ( String1, String2 );
Konkrete Beispiele für Integer- und Stringkopieren
siehe Programme SortLibTest.mod und SimpleSort.

In anz wird die Anzahl der Array-Elemente übergeben.

In size wird die Größe eines Array-Elements übergeben. Im allgemeinen
TSIZE ( Irgentwas ). Für INTEGER z.B. TSIZE ( INTEGER ).

Beispielprogramme:
Im Programm SortLibTest werden Integer- und Stringfelder sortiert und
die Sortierzeiten angegeben. Wie zu sehen arbeitet Quicksort zwei mal
schneller als Heapsort.

Das Programm SimpleSort ist ein einfaches CLI-Programm zum Sortieren von
Files. SimpleSort schlägt knapp das AmigaDos Sort, kommt aber
nicht an die Geschwindigkeit von ARP Sort heran, weil deren QuickSort-
Routine in Maschinensprache geschrieben ist.
Mit SimpleSort kann man sich z.B. das Lexikon des Programms 
Rechtschreib sortieren. Auch ( hoffentlich ) auf dieser Diskette 
vorhanden.

Geschwindigkeitstest mit lexikon.lex im ram:
SimpleSort 10,24 s
DOSSort    10,66 s
ARPSort     4,26 s