Getting Stack overflow Exception while sorting an array with 15000+ elements

Question

This is my quick sort algorithm implementation. I'm getting System.StackOverflowException with the message 'Exception of type 'System.StackOverflowException' was thrown.' while trying to sort an array larger than 15k elements. I actually checked with 15000, 19000, 20000, 30000 elements, and the exception was thrown for the last 3 inputs.

private static int ArraySplitter(int[] intArr, int low, int high)
{
    int pivot = intArr[high];
    int lowIndex = (low - 1);
    for (int i = low; i < high; i++)
    {
        if (intArr[i] <= pivot)
        {
            lowIndex++;
            int temp = intArr[lowIndex];
            intArr[lowIndex] = intArr[i];
            intArr[i] = temp;
        }
    }
    int tempHigh = intArr[lowIndex + 1];
    intArr[lowIndex + 1] = intArr[high];
    intArr[high] = tempHigh;
    return lowIndex + 1;
}
private static void QSort(int[] intArr, int low, int high)
{
    if (low < high)
    {
        int index = ArraySplitter(intArr, low, high);
        QSort(intArr, low, index - 1);
        QSort(intArr, index + 1, high);
    }
}
public static void QuickSort(int[] intArr)
{
    QSort(intArr, 0, intArr.Length - 1);
}

My python implementation also breaking for an array with larger than 5000 elements. Here is my python code -

def QUICKSORT(arr, p, r):
    if p < r:
        q = PARTITION(arr, p, r)
        QUICKSORT(arr, p, q-1)
        QUICKSORT(arr, q+1, r)


def PARTITION(arr, p, r):
    x = arr[r]
    i = p-1
    for j in range(p, r-1):
        if arr[j] <= x:
            i = i + 1
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
    temp = arr[i+1]
    arr[i+1] = arr[r]
    arr[r] = temp
    return i+1

I followed the pseudocode from Thomas H Cormen's Introduction to algorithms.

What's seems to be the problem and how to fix this issue?

In that case, I'm going to assume that the code is valid and the call stack is genuinely running out of space. I'd recommend writing this non-recursively. Also take a look at [this answer](https://stackoverflow.com/a/54584830/3181933) _and pay attention to the warning_. — ProgrammingLlama, Oct 29 '20 at 02:56
@John QuickSort (or any other "split in half" sorting) can't really crash on 30K items - it's about 15 levels of recursion - this is far less than you average ASP.Net stack trace... It is theoretically possible to setup data for QuickSort with non-randomized partition selector, but I doubt OP come up with one. — Alexei Levenkov, Oct 29 '20 at 04:45
@AlexeiLevenkov I just translated the pseudocode for quicksort written in Cormen's Introduction to algorithms book. — Mahmudul Hasan, Oct 29 '20 at 04:57
Here is similar question: https://stackoverflow.com/q/33452614/5311735 — Evk, Oct 29 '20 at 05:16
Sorry I missed ` lowIndex++;` when looking at the code... It is plausible code should work... As pointed out by @Evk depending on input this code will fall into very deep recursion... (deleted my comment) — Alexei Levenkov, Oct 29 '20 at 05:28
Sorry, my bad, changed the pivot, still getting the same error :( — Mahmudul Hasan, Oct 29 '20 at 05:31

rcgldr · Accepted Answer · 2020-11-01T16:52:28.580

Choosing the first or last element in a sub-array for pivot leads to worst case space complexity O(n) if the data is already sorted or reverse sorted. For the questions code, swap the middle element with the last element (array[high]) before splitting to handle sorted or reverse sorted data. Still there are other patterns that result in worst case behavior.

Only using recursion for the smaller partition will limit stack space complexity to O(log(n)), but worst case time complexity remains O(n^2).

private static void QSort(int[] intArr, int low, int high)
{
    while (low < high)
    {
        int index = ArraySplitter(intArr, low, high);
        if((index - low) <= (high - index)){
            QSort(intArr, low, index - 1);
            low = index + 1;
        } else {
            QSort(intArr, index + 1, high);
            high = index - 1;
        }
    }
}

Getting Stack overflow Exception while sorting an array with 15000+ elements

1 Answers1