Program LiedSort;

{ Straigt two-way merge sort for a sample sequential file.
  Described on page 164 of "The Art of Computer Programming"
  volume 3 / "Sorting and Searching" by Donald E. Knuth. }

const
  LENGTE = 80;

var
  bestand0, bestand1, bestand2 : text;
  eind0, eind1, eind2, klaar1, klaar2 : boolean;
  regel0, regel1, regel2, sentinel : string[LENGTE];
  kount, k1, k2, grens, maal, malen : LongInt;
  k, keer, keren : byte;

function log2(w : word) : byte;
{        ====                 }
var
  p : word;
  i : byte;

begin
  i := 0;
  p := w;
  while p > 0 do
  begin
    p := p shr 1;
    if p = 0 then Break;
    i := i + 1;
  end;
  log2 := i;
end;

procedure analyse(macht : byte);
{         =======              }
begin
  Reset(bestand0);
  Rewrite(bestand1);
  Rewrite(bestand2);
  eind0 := false;
  kount := 0;
  while (not eind0) do
  begin
    Readln(bestand0, regel0);
    kount := kount + 1;
    if (((kount-1) shr macht) and 1) = 0 then
      Writeln(bestand1, regel0);
    if (((kount-1) shr macht) and 1) = 1 then
      Writeln(bestand2, regel0);
    eind0 := EoF(bestand0);
  end;
  Flush(bestand1);
  Flush(bestand2);
end;

function kast(zin : string) : string;

var
  k, lengte, c : byte;

begin
  lengte := byte(zin[0])-5;
  kast[0] := char(lengte);
  for k := 1 to lengte do
  begin
    c := byte(zin[k+5]);
    if (c >= 65) and (c <= 90) then
      kast[k] := char(c+32)
    else
      kast[k] := char(c);
  end;
end;

procedure synthese(macht : byte);
{         ========              }
begin
  Rewrite(bestand0);
  Reset(bestand1);
  Reset(bestand2);

  grens := 1 shl macht;
  malen := grens * 2;

  klaar1 := false;
  klaar2 := false;
  eind1 := EoF(bestand1);
  eind2 := EoF(bestand2);
  while not (klaar1 and klaar2) do
  begin
    if (not eind1) then Readln(bestand1, regel1);
    eind1 := EoF(bestand1);
    if (not eind2) then Readln(bestand2, regel2);
    eind2 := EoF(bestand2);
    k1 := 1;
    k2 := 1;
    for maal := 1 to malen do
    begin
      if kast(regel1) <= kast(regel2) then
      begin
        Writeln(bestand0, regel1);
        regel1 := sentinel;
        if (eind1) then klaar1 := true;
        if (k1 < grens) then
        begin
          if (not eind1) then Readln(bestand1, regel1);
          eind1 := EoF(bestand1);
          k1 := k1 + 1;
        end;
      end else begin
        Writeln(bestand0, regel2);
        regel2 := sentinel;
        if (eind2) then klaar2 := true;
        if (k2 < grens) then
        begin
          if (not eind2) then Readln(bestand2, regel2);
          eind2 := EoF(bestand2);
          k2 := k2 + 1;
        end;
      end;
      if (klaar1 and klaar2) then Break;
    end;
  end;
  Flush(bestand0);
end;

begin
  sentinel[0] := char(LENGTE);
  for k := 1 to LENGTE do
    sentinel[k] := char($FF);

  Assign(bestand0, 'liedjes.dat');
  Assign(bestand1, 'bestand1.dat');
  Assign(bestand2, 'bestand2.dat');
  analyse(0);
  keren := log2(kount-1);
  Assign(bestand0, 'bestand0.dat');
  for keer := 1 to keren do
  begin
    synthese(keer-1);
    analyse(keer);
  end;
  Assign(bestand0, 'liedjes.uit');
  synthese(keren);
  Close(bestand1);
  Close(bestand2);
  Close(bestand0);
end.