program TesteSortiereListe(input, output);

  type
  tNatZahl = 0..maxint;
  tRefListe = ^tListe;
  tListe = record
             info : tNatZahl;
             next : tRefListe;
           end;

  var
  RefListe : tRefListe;

  procedure SortiereListe (var ioRefListe : tRefListe);
  { sortiert eine lineare Liste aufsteigend }

     var
     SuchZeiger,
     SortierZeiger,
     MerkZeiger : tRefListe;

  begin

    { Ist die Liste leer ?}    
    if ioRefListe <> nil then 
    begin
              
      { Hat die Liste mehr als ein Element? }  
      if ioRefListe^.next <> nil then
      begin

        {Suchzeiger auf Listenanfang setzen}
        SuchZeiger := ioRefListe; 
        while SuchZeiger^.next <> nil do
        begin

           { Sortierung stimmt an dieser Stelle nicht... }
           if SuchZeiger^.info > SuchZeiger^.next^.info then        
           begin

              {Das aktuelle Element an den Listenanfang bringen?}
              if SuchZeiger^.next^.info < ioRefListe^.info then
              begin
                 MerkZeiger := SuchZeiger^.next;
                 SuchZeiger^.next := SuchZeiger^.next^.next;
                 MerkZeiger^.next := ioRefListe;
                 ioRefListe := MerkZeiger;
              end

              {... oder das aktuelle Element an der richtigen Position in der Liste einfügen?}
              else 
              begin
                 SortierZeiger:=ioRefListe;

                 { Richtige Position in der Liste suchen } 
                 while SortierZeiger^.next^.info < SuchZeiger^.next^.info do
                 begin
                     SortierZeiger:=SortierZeiger^.next;
                 end;

                 { Zeiger an der gefundenen Position umhängen }
                 MerkZeiger := SuchZeiger^.next;
                 SuchZeiger^.next := SuchZeiger^.next^.next;
                 MerkZeiger^.next := SortierZeiger^.next;
                 SortierZeiger^.next := MerkZeiger;
                 end;
           end
           else
               {Mit dem nächsten Element fortsetzen}
               SuchZeiger:=SuchZeiger^.next;
        end; 
      end 
     end;
    end;
    
    
  procedure Anhaengen(var ioListe : tRefListe;
                        inZahl : tNatZahl);
{ Haengt inZahl an ioListe an }
  var Zeiger : tRefListe;
begin
  Zeiger := ioListe;
  if Zeiger = nil then
  begin
    new(ioListe);
    ioListe^.info := inZahl;
    ioListe^.next := nil;
  end
  else
  begin
    while Zeiger^.next <> nil do
      Zeiger := Zeiger^.next;
    { Jetzt zeigt Zeiger auf das letzte Element }
    new(Zeiger^.next);
    Zeiger := Zeiger^.next;
    Zeiger^.info := inZahl;
    Zeiger^.next := nil;
  end;
end;

procedure ListeEinlesen(var outListe:tRefListe);
{ liest eine durch Leerzeile abgeschlossene Folge von Integer-
  Zahlen ein und speichert diese in der linearen Liste RefListe. }
  var
  Liste : tRefListe;
  Zeile : string;
  Zahl, Code : integer;
begin
  writeln('Bitte geben Sie die zu sortierenden Zahlen ein.');
  writeln('Beenden Sie Ihre Eingabe mit einer Leerzeile.');
  Liste := nil;
  readln(Zeile);
  val(Zeile, Zahl, Code); { val konvertiert String nach Integer }
  while Code=0 do
  begin
    Anhaengen(Liste, Zahl);
    readln(Zeile);
    val(Zeile, Zahl, Code);
  end; { while }
  outListe := Liste;
end; { ListeEinlesen }

procedure GibListeAus(inListe : tRefListe);
{ Gibt die Elemente von inListe aus }
  var Zeiger : tRefListe;
begin
  Zeiger := inListe;
  while Zeiger <> nil do
  begin
    writeln(Zeiger^.info);
    Zeiger := Zeiger^.next;
  end; { while }
end; { GibListeAus }

begin
  ListeEinlesen(RefListe);
  SortiereListe(RefListe);
  GibListeAus(RefListe)
end.