/**
 * Sorter.java
 *
 * @author Jeff Ondich
 * @version 2/2/05
 * 
 * Sorter is a box of static methods for sorting arrays of integers.  It
 * also includes a "shuffle" method for generating random arrays.
 */

import javabook.*;

public class Sorter
{
	private static int[] tempArray; // for mergeSort

    public static void main( String[] args )
    {
        if( args.length == 0 )
        {
            System.out.println( "Usage: java Sorter arraySize" );
            System.out.println( "where arraySize specifies the number of integers you want to shuffle and sort." );
            return;
        }

		final int	nItems = java.lang.Integer.parseInt( args[0] );
		tempArray = new int[ nItems ];

		int[]		theItems = new int[nItems];

		shuffle( theItems );

		if( nItems < 30 )
			printArray( theItems );

		long startTime = System.currentTimeMillis();
		mergeSort( theItems );
		long endTime = System.currentTimeMillis();

		if( nItems < 30 )
			printArray( theItems );

		System.out.println( "Sorting time for " + nItems + " items: " + (endTime-startTime) + " ms" );
		System.out.println( "" );
    }


	/**
	 *	Generates a pseudo-random permutation of a.length
	 *	integers.  See p. 139 of "Seminumerical Algorithms,
	 *	2nd edition,"  by Donald Knuth, for more details.
	 */
	public static void shuffle( int[] a )
	{
		int		i, swapIndex, temp;

		for( i=0; i < a.length; i++ )
			a[i] = i;

		for( i=a.length-1; i > 0; i-- )
		{
			swapIndex = (int)Math.floor( Math.random() * (i+1) );
			temp = a[i];
			a[i] = a[swapIndex];
			a[swapIndex] = temp;
		}
	}


	/**
	 * Prints the elements of a[], separated by spaces,
	 * on a line.  Uses System.out.
	 */
	public static void printArray( int[] a )
	{
		for( int i=0; i < a.length; i++ )
			System.out.print( a[i] + " " );
		System.out.println( "" );
	}


	/**
	 * Sorts the array a[] in increasing order.
	 */
	public static void insertionSort( int[] a )
	{
		int			j, k;
		int			temp;

		for( j=1; j < a.length; j++ )
		{
			temp = a[j];
			for( k=j-1; k >= 0  &&  temp < a[k]; k-- )
				a[k+1] = a[k];
			a[k+1] = temp;
		}
	}


	/**
	 * Sorts the array a[] in increasing order.
	 */
	public static void selectionSort( int[] a )
	{
		int			i, j, k;
		int			temp;

		for( j=0; j < a.length - 1; j++ )
		{
			i = j;
			for( k=j+1; k < a.length; k++ )
			{
				if( a[k] < a[i] )
					i = k;
			}

			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}


////////////////////////////////////////////////////////
//
//	Merge()
//	MSort()
//	MergeSort()
//
//	MergeSort sorts the first N elements of the
//	given array in increasing order, using a merge
//	sort algorithm.  Note that MergeSort itself just
//	calls the recursive function MSort, which in
//	turn calls both itself and Merge.  Merge is
//	where most of the work gets done.
//
////////////////////////////////////////////////////////

////////////////////////////////////////////////////////
//	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
////////////////////////////////////////////////////////

	public static void mergeSort( int[] a )
	{
		mSort( a, 0, a.length-1 );
	}


	private static void merge( int[] a, int bottom, int middle, int top )
	{
		int		i = bottom;
		int		j = middle + 1;
		int		k = 0;

		// While both lists still have items in them, merge those
		// items into the temporary array temp[].
		while( i <= middle  &&  j <= top )
		{
			if( a[i] < a[j] )
			{
				tempArray[k] = a[i];
				i++;
			}
			else
			{
				tempArray[k] = a[j];
				j++;
			}
			k++;
		}
	
		// Once one of the lists has been exhausted, dump the other
		// list into the remainder of temp[].
		if( i > middle )
		{
			while( j <= top )
			{
				tempArray[k] = a[j];
				j++;
				k++;
			}
		}
		else
		{
			while( i <= middle )
			{
				tempArray[k] = a[i];
				i++;
				k++;
			}
		}

		// Copy tempArray[] into the proper portion of a[].
		for( i=bottom; i <= top; i++ )
			a[i] = tempArray[i-bottom];
	}


	private static void mSort( int[] a, int bottom, int top )
	{
		if( bottom < top )
		{
			int middle = (bottom + top) / 2;
			mSort( a, bottom, middle );
			mSort( a, middle + 1, top );
			merge( a, bottom, middle, top );
		}
	}
}