// MergeSort

public class MergeSort 
{
    private int [] a;
               
    // make a private copy of the array
    private void copyArray(int [] data)
    {
        a = new int[data.length];
        
        for ( int i = 0; i < data.length; i++ )
        {
            a[i] = data[i];
        }
    }
    
    // copies data into array a and sorts using Merge Sort
    public void sort( int [] data )
    {
        int [] temp = new int[ data.length ];
        
        if ( data == null ) return;
        
        copyArray( data );
        
        mergeSort( 0, a.length - 1, temp );
        
    }
    
    // Sorts the array a, from a[left] through a[right]
    // Using array temp for merging
    // This is the version fo MergeSort found in Weiss
    private void mergeSort( int left, int right, int [] temp )
    {
        int center;
        
        if ( left < right )
        {
            center = ( left + right ) / 2;
            mergeSort( left, center, temp );
            mergeSort( center + 1, right, temp );
            merge( left, center + 1, right, temp );
        }
    }
    
    // Merges two lists, using tempArray to store the results temporarily
    // which are then copied back into a.
    // The left list starts at leftPos and ends at rightPos - 1
    // The right list starts ar rightPos and ends at rightEnd.
    private void merge( int leftPos, int rightPos, int rightEnd, int [] tempArray )
    {
        int leftEnd = rightPos - 1;
        int tempPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        
        // main loop
        while ( leftPos <= leftEnd && rightPos <= rightEnd )
        {
            if ( a[ leftPos ] < a[ rightPos ] )
                tempArray[ tempPos++ ] = a[ leftPos++ ];
            else
                tempArray[ tempPos++ ] = a[ rightPos++ ];
        }
        
        // copy rest of first half
        while ( leftPos <= leftEnd )
            tempArray[ tempPos++ ] = a[ leftPos++ ];
            
        // copy rest of second half
        while ( rightPos <= rightEnd )
            tempArray[ tempPos++ ] = a[ rightPos++ ];
            
        // copy back tempArray
        for ( int i = 0; i < numElements; i++, rightEnd-- )
            a[ rightEnd ] = tempArray[ rightEnd ];
            
    }
        
    
    // return a new copy of the array
    public int[] getSorted()
    {
        int [] ret = new int[a.length];
        
        for ( int i = 0; i < ret.length; i++ )
        {
            ret[i] = a[i];
        }
        
        return ret;
    }

}