Random Pivot QuickSort Not Sorting Correctly

As you can see from the output.txt snapshot. The regular pivot quicksort works correctly, but when a random pivot index is generated it no longer works correctly. Any ideas as to why? When the quicksort method is called, the rand value is true if we want to select and random pivot index and false otherwise if we want to select the last - 1 as the pivot index.

enter code here// QUICK SORT
public static <T extends Comparable<? super T>>
       void quickSort(T[] array, int n, int basecase, boolean rand)
{
    quickSort(array, 0, n-1, basecase, rand);
} // end quickSort

/** Sorts an array into ascending order. Uses quick sort with
 *  median-of-three pivot selection for arrays of at least 
 *  MIN_SIZE elements, and uses insertion sort for other arrays. */
public static <T extends Comparable<? super T>>
       void quickSort(T[] a, int first, int last, int basecase, boolean rand)
{
  if (last - first + 1 < basecase)
  {
    insertionSort(a, first, last);
  }
  else
  {
    // create the partition: Smaller | Pivot | Larger
    int pivotIndex = partition(a, first, last, rand);

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

// 12.17
/** Task: Partitions an array as part of quick sort into two subarrays
 *        called Smaller and Larger that are separated by a single
 *        element called the pivot. 
 *        Elements in Smaller are <= pivot and appear before the 
 *        pivot in the array.
 *        Elements in Larger are >= pivot and appear after the 
 *        pivot in the array.
 *  @param a      an array of Comparable objects
 *  @param first  the integer index of the first array element; 
 *                first >= 0 and < a.length 
 *  @param last   the integer index of the last array element; 
 *                last - first >= 3; last < a.length
 *  @return the index of the pivot */
private static <T extends Comparable<? super T>>
        int partition(T[] a, int first, int last, boolean rand)
{
  int mid = (first + last)/2;
  sortFirstMiddleLast(a, first, mid, last);

  // Assertion: The pivot is a[mid]; a[first] <= pivot and 
  // a[last] >= pivot, so do not compare these two array elements
  // with pivot.

  // move pivot to next-to-last position in array
  swap(a, mid, last - 1);

  Random r = new Random();
  int pivotIndex = (rand) ? (first + r.nextInt(last - first + 1)) : (last - 1);
  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 + 1; 
  int indexFromRight = last - 2; 
  boolean done = false;
  while (!done)
  {
    // starting at beginning of array, leave elements that are < pivot;
    // locate first element that is >= pivot; you will find one,
    // since last element 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; you will find one, 
    // since first element is <= pivot
    while (a[indexFromRight].compareTo(pivot) > 0)
      indexFromRight--;

    assert a[indexFromLeft].compareTo(pivot) >= 0 && 
           a[indexFromRight].compareTo(pivot) <= 0;

    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

output.txt