/*
	Bruce Maxwell
	CS 231 Fall 2016
	Mergesort example code
 */
import java.util.ArrayList;
import java.util.Random;


/*
	A class that implements mergesort on an array

	Extends the built-in ArrayList class.
 */
public class Mergesort<T extends Comparable<T>> extends ArrayList<T> {

		// constructor
		public Mergesort() {
				super();
		}

		// constructor with a presize argument
		public Mergesort(int presize) {
				super(presize);
		}

		// private method to combine two sorted lists into the current list
		// The lists are assumed to have the first element in position 0
		private void merge( Mergesort<T> left, Mergesort<T> right ) {
				int l=0, r=0, i=0;

				while(l<left.size() || r<right.size()) {
						if(l >= left.size()) { // check if left array is done
								this.set(i++, right.get(r++) );
						}
						else if( r >= right.size() ) { // check if right array is done
								this.set(i++, left.get(l++) );
						}
						else { // compare and get the smaller element
								if( left.get(l).compareTo( right.get(r) ) <= 0 ) {
										this.set(i++, left.get(l++) );
								}
								else {
										this.set(i++, right.get(r++) );
								}
						}
				}
				return; 
		}

		// public method to sort the ArrayList in place.
		// Uses NLogN memory, because it must create new arrays
		// for each level of recursion.  The arrays are re-used
		// on the return from recursion.
		public void mergesort() {
				// base case
				if( this.size() <= 1 )
						return;

				// split the array into two parts
				Mergesort<T> left = new Mergesort<T>( this.size()/2 );
				Mergesort<T> right = new Mergesort<T>( this.size()/2 );
				for(int i=0;i<this.size()/2;i++) {
						left.add( this.get(i) );
				}
				for(int i=this.size()/2;i<this.size();i++) {
						right.add( this.get(i) );
				}

				// sort the two parts
				left.mergesort();
				right.mergesort();

				// merge the two parts
				this.merge( left, right );

				return;
		}

		// test function for merge sort
		public static void main(String[] argv) {
				Random gen = new Random();
				int N = 10;
				Mergesort<Integer> numbers = new Mergesort<Integer>();

				if(argv.length > 0 ) {
						N = Integer.parseInt(argv[0]);
				}

				for(int i=0;i<N;i++) {
						numbers.add( gen.nextInt( N * 2) );
						System.out.println( numbers.get(i) );
				}

				long start = System.currentTimeMillis();
				numbers.mergesort();
				long end = System.currentTimeMillis();

				System.out.println("******************");
				for(int i=0;i<N;i++) {
						System.out.println( numbers.get(i) );
				}
				
				System.out.println("******************");
				System.out.println("Time: " + (end - start));
				System.out.println("******************");
				

		}

}