/* ***************************************************************************
 $Workfile: MergeSorterCode.java$
   $Author: kalcock$
     $Date: 02/06/07 18:06:32$
 $Revision: 3$
 *****************************************************************************
 Package
 ****************************************************************************/
package com.keithalcock.t180;
/* ***************************************************************************
 Imports
 ****************************************************************************/

/* ***************************************************************************
 Class
 ****************************************************************************/
public class MergeSorterCode {

    protected static int copyArrayFromTo(int[] fromArray,int fromStart,int fromStop,
            int[] toArray,int toIndex) {
        for (int fromIndex=fromStart;fromIndex<fromStop;fromIndex++)
            toArray[toIndex++]=fromArray[fromIndex];
        return toIndex;
    }   
    
    protected static int[] merge(int[] leftArray,int[] rightArray) {
        int leftLength=leftArray.length,rightLength=rightArray.length;
        int[] middleArray=new int[leftLength+rightLength];
        int leftIndex=0,rightIndex=0,middleIndex=0;
        
        while (leftIndex<leftLength && rightIndex<rightLength)
            if (leftArray[leftIndex]<=rightArray[rightIndex])
                middleArray[middleIndex++]=leftArray[leftIndex++];
            else
                middleArray[middleIndex++]=rightArray[rightIndex++];
        middleIndex=copyArrayFromTo(leftArray,leftIndex,leftLength,middleArray,middleIndex);
        middleIndex=copyArrayFromTo(rightArray,rightIndex,rightLength,middleArray,middleIndex);        
        return middleArray;
    }

    public static int[] sort(int[] unsortedArray) {
        int unsortedLength=unsortedArray.length;
        
        if (unsortedLength<=1)
            return unsortedArray;

        int leftLength=unsortedLength/2;
        int[] leftArray=new int[leftLength];
        copyArrayFromTo(unsortedArray,0,leftLength,leftArray,0);        
        
        int rightLength=unsortedLength-leftLength;
        int[] rightArray=new int[rightLength];
        copyArrayFromTo(unsortedArray,leftLength,unsortedLength,rightArray,0);
        
        return merge(sort(leftArray),sort(rightArray));
    }
    
    protected static boolean isSorted(int[] array) {
        for (int i=0;i<array.length-1;i++)
            if (!(array[i]<=array[i+1]))
                return false;
        return true;
    }    
    
    protected static int testIndex=0;  
    
    protected static void testMergeSorter(int[] testArray) {
        testIndex++;
        System.out.println("Test "+testIndex+" passed? "+
                isSorted(MergeSorterCode.sort(testArray)));       
    }
    
    public static void main(String[] args) {          
        testMergeSorter(new int[]{});
        testMergeSorter(new int[]{10});
        testMergeSorter(new int[]{10,-10});
        testMergeSorter(new int[]{1,2,3,4,5});        
        testMergeSorter(new int[]{-1,2,-3,4,-5});        
        testMergeSorter(new int[]{5,4,3,2,1});        
    }    
}
/* **************************************************************************/