{========================================================
	mergesort.p
	
	Started by Jeff Ondich some time in 1996
	Last modified 3/5/97
	
	This program contains an implementation of Merge
	Sort for integer arrays, as well as a couple of
	procedures that help us test sorting algorithms.
 ========================================================}
 
#include        <gpc-graphics.h>

program		sort( input, output );

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

var		numbers : IntArray;
		N : 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
	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;

{========================================================
	MAIN PROGRAM
 ========================================================}
begin {main program}

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


  { Initialize the random number generator. }
	srandom(gettime);

  { 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 )
end.