Quicksort causing stack overflow

Question

I have implemented a quicksort of an array of integers as follows:

public void Quicksort(int left, int right)
{
    /* The recursive quicksort algorithm consists of four steps:
     * 1. If there are one or less elements in the array to be sorted, return immediately.
     * 2. Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.)
     * 3. Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot.
     * 4. Recursively repeat the algorithm for both halves of the original array.
     */

    int pivot = dataTable[left];

    int l_hold = left;
    int r_hold = right;

    while (left < right)
    {
        while ((dataTable[right] >= pivot) && (left < right))
            right--;

        if (left != right)
        {
            dataTable[left] = dataTable[right];
            left++;
        }

        while ((dataTable[left] <= pivot) && (left < right))
            left++;

        if (left != right)
        {
            dataTable[right] = dataTable[left];
            right--;
        }
    }

    dataTable[left] = pivot;
    pivot = left;
    left = l_hold;
    right = r_hold;

    if (left < pivot)
        Quicksort(left, pivot - 1);

    if (right > pivot)
        Quicksort(pivot + 1, right);
}

It runs okay with an array of, say, 500 000 randomly generated integers. If I fill the array with ascending or descending integers, the quicksort causes a StackOverflowException at around 8800 elements.

I spy with my little eye no clear reason for this. Can you spy a reason with your huge amounts of pairs of eyes? I could go and just find a copypasta of functioning quicksort, but I'd rather find the reason as to what's causing the problem.

The method works on an array that's part of the class and is usually called with (index 0, last index - 1). Thousands of thanks in advance!

You're recursing way too deep. You only have about 1Mb of stack space to work with, and after you use it up you get this error. The random array probably stops recursing fairly soon because it will hit an equal number. The ascending/descending will do the full depth of values every time because of how you'd set it up. This means you recurse levels deep. — steveg89, Dec 13 '13 at 18:09
You might want to consider, to go from a recursive design to an iterative one. I would suggest to check out this thread: http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration — MrPaulch, Dec 13 '13 at 18:12

score 0 · Answer 1 · edited May 23 '17 at 12:06

0

You're experiencing Tail recursion. Put simply, the C# compiler doesn't do a very good job with it. I've read that if you have issues with this in debug, you can try compiling in release mode with optimizations and it will alleviate the issue.

There is way more detailed info here.

edited May 23 '17 at 12:06

Community

1
1

answered Dec 13 '13 at 18:13

Allan Elder

4,052
17
19

score 0 · Answer 2 · answered Dec 13 '13 at 19:14

0

You need to add the stop condition.

function() {

if(value == 0) {
break;
} else {
 function())
}

You can't be calling Quicksort all the time. It needs the stop/break condition.

answered Dec 13 '13 at 19:14

iefpw

6,816
15
55
79

Quicksort causing stack overflow

2 Answers2