My quicksort implementation is using way too many comparisons but cannot determine why

Question

I am trying to implement quicksort in java and I am struggling to implement it in an efficient manner. I believe the problem is with my recursive calls but I cannot determine how to fix it. I am using compares to see how many times comparisons are made in hopes of determining where the problem is. The only thing I can think of is requiring a conditional around my recursive statements because the amount of compares needed is the same whether the inputted array is already sorted or seemingly randomized.

public int quickSort(int[] arr, int left, int right) {

    //left is lowest index
    //right is highest index

    int compares = 0;

    //calls insertion sort once subsets get smaller than 7 elements
    if (right - left < 6) {
      compares += insertSort(arr, left, right);
      return compares;
    }

        //calculate random pivot
        int pivotIndex = randomInt(left, right);
        int pivotValue = arr[pivotIndex];


        //moves pivot value to rightmost index
        int temp;
        temp = arr[pivotIndex];
        arr[pivotIndex] = arr[right];
        arr[right] = temp;

        int pivotFinal = left;


        //determines how many values are lower than the pivot, swapping 
        //smaller values with larger values along the way
        for (int i = left; i < right; i++) {
            compares++;
            if (arr[i] <= pivotValue) {
                temp = arr[i];
                arr[i] = arr[pivotFinal];
                arr[pivotFinal] = temp;
                pivotFinal++;
            }
        }

        //moves pivot to final position so that quicksort is complete
        temp = arr[pivotFinal];
        arr[pivotFinal] = arr[right];
        arr[right] = temp;

        compares += quickSort(arr, left, pivotIndex - 1);
        compares += quickSort(arr, pivotIndex + 1, right);
        return compares;
}



public void main() {
    QuickSort qs = new QuickSort();

    int n = 60;
    int[] array = qs.GenerateRandomSequence(n);

    int compares = qs.quickSort(array);
}

With an n of 60, one of the sequences required more than 4 million compares, which is much, much worse than the actual worst case runtime.

Answer 1

You have a couple of bugs with your indexes. Your recursion needs to be using your final pivot position.

compares += quickSort(arr, left, pivotFinal - 1);
compares += quickSort(arr, pivotFinal + 1, right);

And you're treating your "right" index differently in different spots. Probably easiest to just use "<=" in your loop

for (int i = left; i < right; i++) // assumes right is after the last index

arr[pivotIndex] = arr[right]; // assumes right IS the last index