{***************************************************************************}
{*                         QUICK-SORT                                      *}
{***************************************************************************}

PROCEDURE QSort(Von, Bis : Index);
  {Modifizierter, nichtrekursiver Quicksort mit eigenem Stack}

  TYPE  LIFO      = ^LIFOListe;
        LIFOListe = RECORD v,b : Index; last : LIFO END;

  VAR m       : DirEintrag;
      i, j    : Index;
      Stack   : LIFO;

  PROCEDURE Push(von,bis:Index);
    VAR p : LIFO;
    BEGIN
      new(p); p^.v:=von; p^.b:=bis; p^.last:=Stack; Stack:=p
    END;

  PROCEDURE Pop(VAR von,bis:Index);
    VAR p : LIFO;
    BEGIN
      p:=Stack; von:=p^.v; bis:=p^.b; Stack:=p^.last; dispose(p)
    END;


  PROCEDURE vertausche(d1,d2:Index);
    VAR temp : DirEintrag;
    BEGIN temp:=Directory[d1]; Directory[d1]:=Directory[d2];
          Directory[d2]:=temp
    END;

  FUNCTION kleiner(x,y:DirEintrag):boolean;
    VAR h : boolean;
    BEGIN
      h:=false;
      IF x.Name<y.Name
          THEN h:=true
          ELSE IF x.Name=y.Name
                 THEN IF x.DskNr<y.DskNr
                        THEN h:=true
                        ELSE IF x.DskNr=y.DskNr THEN h:=x.User<y.User;
      kleiner:=h
    END;

  PROCEDURE ESort(Von, Bis : Index);
    {Einfuege-Sort fuer kleine Listen}
    VAR i,j,m : Index;
    BEGIN
      FOR i:=Von TO Bis-1 DO
        BEGIN m:=i;
          FOR j:=i+1 TO Bis DO
            IF kleiner(Directory[j],Directory[m]) THEN m:=j;
          IF m<>i THEN vertausche(i,m)
        END
    END;

  BEGIN  {QSort}
    Stack:=NIL; push(Von,Bis);
    REPEAT
     Pop(Von,Bis);
     IF Bis-Von<7 THEN ESort(Von,Bis)
     ELSE
     BEGIN
       i:=Von; j:=Bis; m:=Directory[(i+j) DIV 2];
       REPEAT
         WHILE kleiner(Directory[i],m) DO i:=succ(i);
         WHILE kleiner(m,Directory[j]) DO j:=pred(j);
         IF i<=j THEN BEGIN vertausche(i,j); i:=succ(i); j:=pred(j); END
       UNTIL i>j;
       IF i<Bis THEN Push(i,Bis);
       IF j>Von THEN Push(Von,j)
     END
    UNTIL Stack=NIL
  END;   {QSort}