Stack Overflow on Quicksort with a first element pivot in Java

Question

For this assignment I'm supposed to test my quicksort class using a variety of different pivots and a variety of ArrayLists in different arrangements. The class works fine with a random pivot, or a median of three pivot, but when using the first element as my pivot, I get a stack overflow error on both tests with a nearly sorted list and a list in descending order. My test sizes are fairly large, starting at 10,000 and going to 100,000, but only these two tests give me a stack overflow error and I'm not sure why. Here's the code for my Quicksort class:

public class QuickSorter<E extends Comparable<? super E>> implements Sorter<E> {

    private PivotChooser<E> chooser;

    /**
     * QuickSorter Constructor
     * 
     * @param chooser PivotChooser object used to determine how the pivot is chosen
     */
    public QuickSorter(PivotChooser<E> chooser) {
        this.chooser = chooser;
    }

    /**
     * Quicksort Driver method. Ensures the list isn't empty before calling the
     * recursive Quicksort method
     */
    public void sort(ArrayList<E> list) {

        if (list.size() < 0)
            throw new IllegalArgumentException();

        int leftIndex = 0;
        int rightIndex = list.size() - 1;

        recursiveSort(list, leftIndex, rightIndex);

    }

    /**
     * Recursive Quicksort method
     * 
     * @param list       Unsorted, Generic list
     * @param leftIndex  The lowest index of the partition
     * @param rightIndex The highest index of the partition
     */
    private void recursiveSort(ArrayList<E> list, int leftIndex, int rightIndex) {
        
        if (leftIndex < rightIndex) {
            int partition = partition(list, leftIndex, rightIndex);

            recursiveSort(list, leftIndex, partition - 1);
            recursiveSort(list, partition + 1, rightIndex); //This is the line that seems to cause the Stack Overflow error
        }

    }

    /**
     * Quicksort Partition method that grabs the pivot from the chooser object and
     * sorts the partition
     * 
     * @param list       Unsorted, Generic list
     * @param leftIndex  The lowest index of the partition
     * @param rightIndex The highest index of the partition
     * @return The current pivot index
     */
    private int partition(ArrayList<E> list, int low, int high) {
        int pivotIndex = chooser.getPivotIndex(list, low, high);
        E pivot = list.get(pivotIndex);
        swap(list, pivotIndex, high);

        int i = low;

        for (int j = low; j <= high; j++) {
            E temp = list.get(j);
            if ((temp.compareTo(pivot) < 0)) {
                swap(list, i, j);
                i++;
            }
        }

        swap(list, i, high);

        return i;
    }


    /**
     * Swaps two given elements in a given ArrayList
     * 
     * @param list   The given ArrayList
     * @param index1 The first element index to swap
     * @param index2 The second element index to swap
     */
    private void swap(ArrayList<E> list, int index1, int index2) {
        E temp = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, temp);
    }

public class FirstPivotChooser<E extends Comparable<? super E>> implements PivotChooser<E> {

    /**
     * Returns the left-most index in a given ArrayList
     * 
     * @param list       The generic ArrayList
     * @param leftIndex  The left-most or lowest index in the list
     * @param rightIndex The right-most or highest index in the list
     * @return The left-most index
     */
    public int getPivotIndex(ArrayList<E> list, int leftIndex, int rightIndex) {

        return leftIndex;

    }
}

Answer 1

This is a common issue when implementing quicksort with recursive calls both for the left and the right partition. In case one of the two partitions has almost all the elements of the original subarray -- in the extreme: all except the pivot --, and this continues like that also in the deeper recursive calls, then the recursion depth will amount to O(𝑛), which means that for large arrays you will fully consume the available call stack space and hit a stack overflow error.

Wikipedia's entry on quicksort describes the solution, ensuring a O(log𝑛) worst case auxiliary space complexity:

To make sure at most O(log 𝑛) space is used, recur first into the smaller side of the partition, then use a tail call to recur into the other, or update the parameters to no longer include the now sorted smaller side, and iterate to sort the larger side.

[...]

After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(log 𝑛) space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack.

To implement this idea, modify recursiveSort so it has a loop that continues to work on the greatest of the two produced partitions, while it defers the work for the other, smaller, partition to a recursive call:

    private void recursiveSort(ArrayList<E> list, int leftIndex, int rightIndex) {
        while (leftIndex < rightIndex) {
            int partition = partition(list, leftIndex, rightIndex);
            // Determine which of the two is the greater partition:
            if (partition - leftIndex > rightIndex - partition) {
                // Use recursion for sorting the smaller partition:
                recursiveSort(list, partition + 1, rightIndex);
                // Use iteration for sorting the greater partition:
                rightIndex = partition - 1; 
            } else { // Idem: but the other way round
                recursiveSort(list, leftIndex, partition - 1);
                leftIndex = partition + 1;
            }
        }
    }