import java.util.Arrays;

/**
 * The sort method of this class sorts an array, using the quick sort algorithm.
 */
public class QuickSorter
{
    /**
     * Sort an array, using quick sort.
     * @param a the array to sort
     */
    public static void sort(int[] a)
    {
        sort(a, 0, a.length - 1);
    }

    /**
     * Sort a portion of an array, using quick sort.
     * @param a the array to sort
     * @param from the first index of the portion to be sorted
     * @param to the last index of the portion to be sorted
     */
    public static void sort(int[] a, int from, int to)
    {
        if (from >= to) return;  // base case

        int p = partition(a, from, to);
        
        sort(a, from, p);
        sort(a, p+1, to);
    }

    /**
     * Partition a portion of an array.
     * @param a the array to partition
     * @param from the first index of the portion to be partitioned
     * @param to the last index of the portion to be partitioned
     * @return the last index of the first partition
     */
    private static int partition(int[] a, int from, int to)
    {
        int pivot = a[from];
        int i = from - 1;
        int j = to + 1;
        
        while (i < j) {
            
            // Move i to the right.
            i++;
            while (a[i] < pivot) {
                i++;
            }
            
            // Move j to the left.
            j--;
            while (a[j] > pivot) {
                j--;
            }
            
            // Swap.
            if (i < j) {
                ArrayUtil.swap(a, i, j);
            }
        }
        
        return j;  // index of the pivot
    }
}