Recursive functions work fine separately, but together cause stack overflow error

Question

While working on the Dutch National Flag Problem, I came up with the following code, hoping to implement my own variant of quicksort:

static void sort(int[] nums) {
    dutchSort(nums,0,nums.length);
}

// sorts nums[left..right)
static void dutchSort(int[] nums, int left, int right) {
    // recursion base case
    if (left >= right) return;

    int pivot = nums[left];

    // smaller - index of the last element smaller than pivot value
    // equal - index of the last element equal to pivot value
    // larger - index of the first element larger than pivot value
    int smaller = left-1, equal = left, larger = right, temp;

    // before sorting is completed, 'equal' is the current index,
    // much like 'i' in a for-loop
    while (equal < larger) {
        if (nums[equal] < pivot) {
            temp = nums[equal];
            nums[equal] = nums[++smaller];
            nums[smaller] = temp;
        } else if (nums[equal] == pivot) {
            equal++;
        } else {
            temp = nums[equal];
            nums[equal] = nums[--larger];
            nums[larger] = temp;
        }
    }

    // recursively sort smaller subarray
    dutchSort(nums, 0, smaller+1);

    // recursively sort larger subarray
    dutchSort(nums, equal, nums.length);
}

The resulting sorted array should ideally consist of 3 subarrays: (i) all values smaller than pivot, (ii) all values equal to the pivot, (iii) all values greater than pivot. Then subarrays (i) and (iii) are recursively sorted until the base case of a subarray of size 1 is sorted. I think my code correctly does this, but I'm not 100% sure. The logic in the while loop, and the values used for left and right in the recursive calls are also correct.

However, the two recursive calls at the end of the dutchSort function, dutchSort(nums, 0, smaller+1); and dutchSort(nums, equal, nums.length);, cause a stack overflow error.

When I comment out both or exactly one of the recursive functions, the program terminates and produces a correctly sorted (or partially sorted) array.

Sample input (with both recursive functions commented out), and including a print statement for smaller:

[2,0,1,0,0,2]

Output:

smaller = 3
[0, 1, 0, 0, 2, 2]

While not actually sorted, this is still a correct output since all values to the pivot's left are lesser values. Then ideally, the two recursive functions would take care of the appropriate subarrays. In this exact case, only the smaller subarray [0,1,0,0] needs to be sorted. Notice that smaller = 3 correctly shows that the subarray from indices [0..3] needs to be sorted.

Restarting the program with input [0,1,0,0], again with recursive functions commented out, I correctly get:

[0,0,0,1]

So it appears the sorting logic is correct; the original array is sorted correctly, and manually sorting the appropriate subarrays works as well. But when everything is un-commented and combined, there's a loop that causes a stack overflow.

Please help me figure out the cause of this behavior.

Thanks :)

Answer 1

I think your first recursive call should use left as second parameter:

dutchSort(nums, left, smaller+1)

instead of

dutchSort(nums, 0, smaller+1)