/**
 *  <PRE>
 *  MergeSort.java
 *
 *  Revisions: 1.0 Nov. 04, 2002
 *               Created the MergeSort class
 *			   1.1 Nov. 05, 2002
 *				 Compiled, Finished, Commented
 *
 *  </PRE>
 *
 *	Collaboration Statement:
 *    I worked on the homework assignment alone, using only             
 *    course materials.
 *  
 *  Created with JCreatorLE, some indents are off when viewed through notepad
 *    or EMACS
 *
 *  @author <A HREF="mailto:gtg184g@mail.gatech.edu">Jose Manuel Caban</A>
 *  @version Version 1.1, Nov. 04, 2002
 */

public class MergeSort extends AbstractSort{
	
  ////////////////
  //Constructors//
  ////////////////
  
  /**
   *Constructor for MergeSort
   *@param arrayWrap, the array to be sorted
   */
  public MergeSort(ArrayWrapper arrayWrap){
    super(arrayWrap);
    
  }
 	
  ///////////
  //Methods//
  ///////////
	
  /**
   *Sort the Array
   */
  public void doSort(){
    Comparable[] tmpArray = new Comparable[arrayWrap.length()];
    for(int i=0; i<arrayWrap.length(); i++){
    	tmpArray[i] = arrayWrap.get(i);
    }
    mergeSort(tmpArray,0,tmpArray.length-1);    
  }//end doSort()
  
  /**
   *Recursive Function to sort 2 arrays
   */
  private void mergeSort(Comparable[] toSort, int iLeft, int iRight){
  	if(iLeft < iRight){
  		int center = (iLeft+iRight)/2;
  		mergeSort(toSort,iLeft,center);
  		mergeSort(toSort,center+1,iRight);
  		merge(toSort,iLeft,center+1,iRight);
  	}
  }//end mergeSort()
  
  /**
   *Merge arrays
   */
  private void merge(Comparable[] toSort, int iLeft, int iCenter, int iRight){
  	int iLeftCounter 	= iLeft;
  	int iRightCounter 	= iCenter;
  	int iTempCounter  	= iLeft;
  	int iLength			= (iRight - iLeft) + 1;
  	
  	
  	while(iLeftCounter<=(iCenter-1) && iRightCounter<= iRight){
  		if(arrayWrap.get(iLeftCounter).compareTo(
  					arrayWrap.get(iRightCounter))<0){
  			toSort[iTempCounter++] = arrayWrap.get(iLeftCounter++);
  		}
  		else{//you're off your rocker if you think im gonna write the if()
  			toSort[iTempCounter++] = arrayWrap.get(iRightCounter++);
  		}
  	}
  	
  	while(iLeftCounter <= (iCenter-1)){
  		toSort[iTempCounter++] = arrayWrap.get(iLeftCounter++);
  	}
  	
  	while(iRightCounter <= iRight){
  		toSort[iTempCounter++] = arrayWrap.get(iRightCounter++);
  	}
  	
  	for(int i=0; i<iLength; i++,iRight--){
  		arrayWrap.set(iRight,toSort[iRight]);
  	}
  }//end merge()


  /**
   *  Debugging main for class MergeSort.  
   *  This method will rigorously test my code.
   *
   *  <br><br>
   *  @param args a String array of command line arguments.
   */
  public static void main(String[] args) {
    ArrayWrapper aw = new ArrayWrapper(ArrayWrapper.getRandomIntegerArray(40));    
    MergeSort M$ = new MergeSort(aw); //ok, actually i HATE ppl who say M$
    							//except T.A.'s who say it..
    
    for(int i=0;i<aw.length();i++){
    	System.out.println(aw.get(i));
    }
    M$.doSort();
    System.out.println("\n/****Testing Now****/\n");
    for(int i=0;i<aw.length();i++){
    	System.out.println(aw.get(i));
	}
    
  }// end of main(String[] args)

}// end of class MergeSort