PROGRAM Merge (Input,Output);

CONST
   MaxSize = 5000;

   m = 100000000;   {random num generator}     
   b = 31415821;
   m1 = 10000;

TYPE
   ArrayType = Array[1..MaxSize] of Integer;
   
VAR
   Arr1, Arr2, ArrM : ArrayType;
   NumTests, Size, MaxKey : Integer;
   RandNum, QSCount : Integer4;
   Another : Char;
   i, j, k, ResSize : Integer;
   Again : Boolean;






{Generate a pseudo-random number between 0 and 1.
RandNum should be seeded at start of each program. }

FUNCTION Random : Real;


FUNCTION Mult (p, q :Integer4) : Integer4;
Var 
   p1 , p0, q1, q0 : Integer4;
Begin
   p1 := p DIV m1;
   p0 := p MOD m1;
   q1 := q DIV m1;
   q0 := q MOD m1;
   Mult := (((p0*q1 + p1*q0) MOD m1) * m1 + p0*q0) MOD m;
End;


Begin
   RandNum := (Mult(RandNum,b) + 1) MOD m;
   Random := RandNum / m;
End;





PROCEDURE QuickSort (Var A : ArrayType;
                     left, right : Integer);
Var
   p, i, j, temp : Integer;
Begin
   IF left < right THEN
    Begin
     p := left;
     i := left + 1;
     j := right;
     REPEAT
       WHILE (A[i] <= A[p]) AND (i <= j) DO
        Begin
          QSCount := QSCount + 1;
          i := i + 1;
        End;
       WHILE (A[j] > A[p]) AND (i <= j) DO
        Begin
          QSCount := QSCount + 1;  
          j := j - 1;
        End;
       IF i < j THEN
        Begin
         temp := A[i];
         A[i] := A[j];
         A[j] := temp;
         i := i + 1;
         j := j - 1;
        End;
     UNTIL j < i;
     temp := A[j];
     A[j] := A[p];
     A[p] := temp;
     p := j;
     QuickSort(A,left,p-1);
     QuickSort(A,p+1,right);
    End;

End;






PROCEDURE FillArray (VAR TestArray : ArrayType;
                     Size, MaxKey : Integer);
Var
   i, j : Integer;
 
Begin
   FOR i := 1 to Size DO
    Begin
      TestArray[i] := Trunc(Random * MaxKey);
     { Writeln(TestArray[i]);}
    End;

{  i := 1;
   REPEAT
       FOR j := 0 TO 4 DO
         Write(TestArray[i+j]);
       Writeln;
       i := i + 5;
    UNTIL i >= Size;}
End;







PROCEDURE Merge (Var A1 : ArrayType; Size1 : Integer; 
                 Var A2 : ArrayType; Size2 : Integer;
                 Var A : ArrayType;
                 Var SizeA : Integer);
VAR
   i,j,k : Integer;

Begin
   i := 1;
   j := 1;
   k := 1;

   WHILE (i <= Size1) AND (j <= Size2) DO
     Begin
       IF A1[i] <= A2[j] THEN
         Begin
           A[k] := A1[i];
           i := i + 1;
         End
       ELSE
         Begin
           A[k] := A2[j];
           j := j + 1;
         End;
       k := k + 1;
     End;

   IF i > Size1 THEN
     WHILE j <= Size2 DO
       Begin
         A[k] := A2[j];
         j := j + 1;
         k := k + 1;
       End
   ELSE
     WHILE i <= Size1 DO
       Begin
         A[k] := A1[i];
         i := i + 1;
         k := k + 1;
       End;

   SizeA := Size1 + Size2;
End;
     

   
BEGIN

   Writeln('Seed random number generator');
   Readln(RandNum);

{   Again := True;
   Repeat
      Writeln('Array size?');
      Readln(Size);
      Writeln('Key range?');
      Readln(MaxKey);
      Writeln('Number of tests?');
      Readln(NumTests);
      Test(Size,MaxKey,NumTests);
      Writeln;
      Writeln('Another?');
      Readln(Another);
      If (Another <> 'Y') AND (Another <> 'y') Then
         Again := False;
   Until Not Again;
}


      Writeln('Array size?');
      Readln(Size);
      Writeln('Key range?');
      Readln(MaxKey);

   FillArray(Arr1,Size,MaxKey);
   QuickSort(Arr1,1,Size);
   k := 1;
   REPEAT
      FOR j := 0 TO 4 DO
         Write(Arr1[k+j]);
      Writeln;
      k := k + 5;
   UNTIL k >= Size;  
   FillArray(Arr2,Size,MaxKey);
   QuickSort(Arr2,1,Size);
   k := 1;
   REPEAT
      FOR j := 0 TO 4 DO
         Write(Arr2[k+j]);
      Writeln;
      k := k + 5;
   UNTIL k >= Size;  
   Merge(Arr1,Size,Arr2,Size,ArrM,ResSize);
  
   k := 1;
   REPEAT
      FOR j := 0 TO 4 DO
         Write(ArrM[k+j]);
      Writeln;
      k := k + 5;
   UNTIL k >= ResSize;  

END.