// QuickSort

public class QuickSort 
{
    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 Quick Sort
    public void sort( int [] data )
    {
        if ( data == null ) return;
        
        copyArray( data );
        
        quickSort( 0, a.length - 1);
        
    }
    
    // Sorts the array a, from a[left] through a[right]
    // This is the version fo QuickSort is adapted from Weiss
    private void quickSort( int left, int right )
    {
        int pivot, i, j, temp;
        
        if ( left >= right )
            return;
            
        pivot = a[right];
        
        // Partitioning
        for ( i = left - 1, j = right; ; )
        {
            while( ++i <= right && a[ i ] < pivot )
                ;
                
            while( --j >= left && pivot < a[ j ] )
                ;
                
            if ( i < j )
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            else
                break;
        }
        
        // Swap pivot back in
        temp = a[i];
        a[i] = a[right];
        a[right] = temp;
        
        quickSort( left, i - 1 );
        quickSort( i + 1, right );
            
        
    }
    
    // return a new copy of the array
    public boolean checkSorted()
    {
        
        for ( int i = 0; i < a.length - 1; i++ )
        {
            if ( a[i] > a[i + 1] )
                return false;
        }
        
        return true;
    }
    
    // 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;
    }

}