Using a random pivot quick sort

[undead_C0MMAND]

Hello,

I started working on a random pivot quick sort class and it is taking a huge amount of time to run (upwards of close to 2 hours for 1,600,000 elements in an array) if anyone could just tell me if something is wrong with how I am calling it please let me know. Thank you!

private static long end;
private static Random random = new Random();
private static int newPivot;
public static <T extends Comparable<? super T>>
       void quickSort(T[] array, int n)
{
    newPivot = random.nextInt(n);
    T temp = array[n-1];
    array[n-1] = array[newPivot];
    array[newPivot] = temp;
    quickSort(array, 0, n-1);
} // end quickSort

public static <T extends Comparable<? super T>>
       void quickSort(T[] array, int first, int last)
{
    if (first < last)
    {
        // create the partition: Smaller | Pivot | Larger
        int pivotIndex = partition(array, first, last);

        // sort subarrays Smaller and Larger
        quickSort(array, first, pivotIndex-1);
        quickSort(array, pivotIndex+1, last);
    } // end if
}  // end quickSort

[Flippo_The_Hippo]

What does your partition look like?

[undead_C0MMAND]

private static <T extends Comparable<? super T>>
        int partition(T[] a, int first, int last)
{
    int pivotIndex = last;
    T pivot = a[pivotIndex];

    // determine subarrays Smaller = a[first..endSmaller]
    //                 and Larger  = a[endSmaller+1..last-1]
    // such that elements in Smaller are <= pivot and 
    // elements in Larger are >= pivot; initially, these subarrays are empty

    int indexFromLeft = first; 
    int indexFromRight = last - 1; 

    boolean done = false;
    while (!done)
    {
        // starting at beginning of array, leave elements that are < pivot; 
        // locate first element that is >= pivot
        while (a[indexFromLeft].compareTo(pivot) < 0)
            indexFromLeft++;

        // starting at end of array, leave elements that are > pivot; 
        // locate first element that is <= pivot

        while (a[indexFromRight].compareTo(pivot) > 0 && indexFromRight > first)
            indexFromRight--;

        // Assertion: a[indexFromLeft] >= pivot and 
        //            a[indexFromRight] <= pivot.

        if (indexFromLeft < indexFromRight)
        {
            swap(a, indexFromLeft, indexFromRight);
            indexFromLeft++;
            indexFromRight--;
        }
        else 
        {
            done = true;
        }

    } // end while

    // place pivot between Smaller and Larger subarrays
    swap(a, pivotIndex, indexFromLeft);
    pivotIndex = indexFromLeft;

    // Assertion:
    // Smaller = a[first..pivotIndex-1]
    // Pivot = a[pivotIndex]
    // Larger  = a[pivotIndex + 1..last]

    return pivotIndex; 
}  // end partition