{
	mergesort.p

	Started by Jeff Ondich on 2/29/96
	Last modified 2/29/96

	This program asks the user for N, generates a
	random permutation of 1,2,...,N, prints out the
	permutation, sorts it using the Merge Sort
	algorithm, and prints out the sorted array
	so you'll believe the sorting algorithm is
	working.

	You will need to compile this program using
	gpcgraphics.  The random number functions aren't
	available in straight gpc.
}

program		sort( output );

type		IntArray = array[1..10000] of integer;

var		numbers : IntArray;
		N, mergesortcount : integer;



{ PrintList prints the first n items of the given array on a line.
  It is handy for debugging the sorting routines, but you
  won't want to use it when dealing with very large arrays.

  Why do I make "list" a variable parameter?  I don't want
  to change the original, after all.  The reason is that I
  also don't want to make a copy of a 40000-byte array
  every time I call PrintList().  That would be an unnecessary
  waste of memory.
}
procedure PrintList( var list : IntArray; n : integer );
var		i : integer;
begin
	for i := 1 to n do
		write( list[i]:4 );
	writeln
end;


{ Merge  merges two adjacent portions of a given array.

  Preconditions:
	(1) a[bottom],...,a[middle] are in increasing order
	(2) a[middle+1],...,a[top] are in increasing order
	(3) top > middle  and  middle >= bottom

  Postconditions:
	(1) a[bottom],...,a[top] compose the same set of
	    numbers as before, but now in increasing order
	(2) The rest of the array a[] is unchanged
}
procedure Merge( var a : IntArray; bottom, middle, top : integer );
var		temp : IntArray;
		i, j, k : integer;
begin
	i := bottom;
	j := middle + 1;
	k := 0;

  { While both lists still have items in them, merge those
    items into the temporary array temp[] }

	while (i <= middle) and (j <= top) do
	begin
		k := k + 1;
		if a[i] < a[j] then
		begin
			temp[k] := a[i];
			i := i + 1
		end
		else
		begin
			temp[k] := a[j];
			j := j + 1
		end
	end;
	
  { Once one of the lists has been exhausted, dump the other
    list into the remainder of temp[] }

	if i > middle then
	begin
		while j <= top do
		begin
			k := k + 1;
			temp[k] := a[j];
			j := j + 1
		end
	end
	else
	begin
		while i <= middle do
		begin
			k := k + 1;
			temp[k] := a[i];
			i := i + 1
		end
	end;


  { Copy temp[] into the proper portion of a[] }

	for i := bottom to top do
		a[i] := temp[i-bottom+1]
end;



{ MergeSort sorts the items a[bottom],...,a[top] into increasing
  order.  Thus, a call of MergeSort( myArray, 1, N ) will sort
  the entire N-element array "myArray".

  Note that the recursion is stopped by the fact that MergeSort
  does nothing with 1-element lists.
}
procedure MergeSort( var a : IntArray; bottom, top : integer );
var		middle : integer;
begin
mergesortcount := mergesortcount + 1;
	if bottom < top then
	begin
		middle := (bottom + top) div 2;
		MergeSort( a, bottom, middle );
		MergeSort( a, middle + 1, top );
		Merge( a, bottom, middle, top )
	end
end;


{  Shuffle generates a pseudo-random permutation of N integers.
   See p. 139 of "Seminumerical Algorithms, 2nd edition,"
   by Donald Knuth, for more details.
}
procedure Shuffle( var list : IntArray; N : integer );
var
	i, j, temp: integer;
begin
	for i := 1 to N do
		list[i] := i;

	for i := N downto 2 do
	begin
		j :=  (random mod i) + 1;
		temp := list[j];
		list[j] := list[i];
		list[i] := temp
	end
end;


begin {main program}

  { This main program serves as a testing program
    for sorting routines. }


  { Initialize the random number generator. }
	srandom(gettime);
mergesortcount := 0;

  { Get N from user, and generate a random permutation
    of 1,2,...,N.}
	write( 'How many numbers do you wish to sort? ' );
	readln( N );
	Shuffle( numbers, N );

  { Print the unsorted list. }
	PrintList( numbers, N );

  { Sort the list, and print the results. }
	MergeSort( numbers, 1, N );
	PrintList( numbers, N );
writeln( 'MergeSort(): ', mergesortcount );
end.