Quicksort - Worst case results in stack overflow?

Question

I'm trying to implement the quick sort algorithm, where i choose the pivot to be the rightmost element.. However, when the array of ~4000 elements already is sorted, stack overflow occurs. This is my implementation:

void quickSortSimpleAscending(int elements[], int startindex, int endindex)
{

    int pivot = elements[endindex];
    int i = startindex;
    int j = endindex;



    while (i < j)
    {

        while (elements[i] < pivot)
            i++;

        while (elements[j] > pivot)
            j--;


        if (i <= j)
        {
            swap(elements[i], elements[j]);
            i++;
            j--;
        }
    }


    if (startindex < j)
        quickSortSimpleAscending(elements, startindex, j);


    if (i < endindex)
        quickSortSimpleAscending(elements, i, endindex);
}

Is there any way to solve this without using the method "median of three"? Thanks!

If the array is already sorted, you never decrease j, so startindex will always be smaller than j, so you run into an endless loop. It's a bug in your program, not the stack being to small. — JohnB, Nov 19 '15 at 22:16
See also [algorithm - Quicksort worst case](http://stackoverflow.com/q/4019528/643383). — Caleb, Nov 19 '15 at 22:18
@JohnB: Of course, even if that bug is fixed, for a large array with pathological inputs, it could still end up recursing once per element, right? So stack overflow would remain a possibility for huge input arrays (and it would run slow, thanks to the `O(n*n)` runtime in the pathological case for quicksort). — ShadowRanger, Nov 19 '15 at 22:22
Interesting discussion on how to improve quicksort and why heapsort may not be worse or even better if implemented correctly: http://users.aims.ac.za/~mackay/sorting/sorting.html — JohnB, Nov 19 '15 at 22:32

lrleon · Answer 1 · 2015-11-20T03:28:01.553

First of all, it is good to see that your code does not use the median of three to select the pivot. You simply select as pivot the element to the right.

Is there any way to solve this without using the method "median of three"?

The median of three is not in itself the reason why you get a stack overflow. The overflow could occur when through successive and recursive calls bad partitions are obtained; that is, when the pivot causes a left partition to much larger respect to the right partition. In your concrete case, if the array is already sorted, then you will get a left partition of n - 1 elements and a right partition of zero size. The next time you will get a left partition of n - 2 and so on. So the algorithm will perform n recursive calls, which will overflow for modest stack sizes.

The solution

In order to mitigate the risk of an overflow, and in the practice to avoid it, the solution is to sort the smallest partition first. With this approach, the worst case will occur when you get the best partitions; that is, when they tend to be of equal sizes. In this case, the maximum number of successive recursive calls is log(n).

I hope that will be helpful

score 0 · Answer 2 · answered Nov 19 '15 at 22:23

In fact, you will get stack overflow sooner or later if you don't constraints the depth of recursion. One common workaround is to add a fourth parameter to the function to keep track on the depth, and switch to other sorting algorithm when a certain limit is reached.

Quicksort - Worst case results in stack overflow?

2 Answers2

The solution