Why is the pivot element included while sorting the left partition in Quicksort?

I am learning Quicksort from the implementation given in the famous book Cracking the Coding Interview. I understand that the partition function chooses the middle element as the pivot and returns the index where the right partition just starts (inclusive) so the quickSort function will next perform Quicksort recursively on right partition i.e. quickSort(arr, index, right). So far it is good.

The problem is that the left partition now contains the pivot element (at index – 1 location exactly) as well which is already sorted so why is it not doing quickSort(arr, left, index – 2) instead of quickSort(arr, left, index – 1) to skip the pivot element. I tried skipping the pivot but some elements were not sorted properly e.g. with this array: [29, 99, 27, 41, 66, 28, 44, 78, 87, 19, 31, 76, 58, 88, 83, 97, 12, 21, 44]

The complete code is given below:

public class Quicksort {
    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left + (right - left) / 2]; // Pick a pivot point. Can be an element        
        
        while (left <= right) { // Until we've gone through the whole array
            // Find element on left that should be on right
            while (arr[left] < pivot) { 
                left++;
            }
            
            // Find element on right that should be on left
            while (arr[right] > pivot) {
                right--;
            }
            
            // Swap elements, and move left and right indices
            if (left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }
        return left; 
    }
    
    public static void quickSort(int[] arr, int left, int right) {
        int index = partition(arr, left, right); 
        if (left < index - 1) { // Sort left half
            quickSort(arr, left, index - 1);
        }
        if (index < right) { // Sort right half
            quickSort(arr, index, right);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = AssortedMethods.randomArray(20, 0, 6);
        AssortedMethods.printIntArray(arr); 
        quickSort(arr, 0, arr.length - 1);
        AssortedMethods.printIntArray(arr);
    }

}

Answer

The partition function does not necessarily return the index of the pivot. The actual pivot value may be at the left of it or at the right. It really depends when it was encountered and swapped. This can happen some time before left and right cross each other.

For this reason you cannot skip the value at index.

If you want partition to return the index of the pivot value, should swap the pivot value to one side of the current partition before the loop starts, and swap it back into place after the loop finishes — and then you know its index. In that case you can exclude it in the recursive calls. As the pivot value is thus excluded from the loop (unless it is duplicate), the loop condition should be checked at every change of left and right:

public static int partition(int[] arr, int left, int right) {
    int mid = left + (right - left) / 2; 
    int pivot = arr[mid];
    int store = right--;
    swap(arr, mid, store);
    while (left <= right) {
        if (arr[left] < pivot) { 
            left++;
        } else if (arr[right] > pivot) {
            right--;
        } else if (left < right) {
            swap(arr, left, right);
            left++;
            right--;
        } else  {
            return left;
        }
    }
    swap(arr, left, store);
    return left;
}

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int index = partition(arr, left, right); 
        quickSort(arr, left, index - 1);
        quickSort(arr, index + 1, right);
    }
}

The targeted benefit of excluding the value at index from the recursive calls comes with the cost of the extra swaps of the pivot value and more evaluations of the loop condition.