Quick Sort Implementation (Test for failure) in C++

Question

I've given an assignment to implement Quicksort in C++, and I've successfully written code that seems to work. As I tested my algorithm for failure, it crashed when I had it sort numbers in a binary file with a million elements. Note that I have two files with one million elements each. One of them is unsorted, and the other is "almost sorted", and my algorithm seems to only fail when sorting the "almost sorted" file. Here's what my code looks like:

    int partition(int arr[], int low, int high) 
{
    int pivotI = low; //pivot index
    int pivot = arr[pivotI];
    int temp = arr[low];
    arr[low] = pivot;
    arr[pivotI] = temp;
    int partitionI = low;
    low++;
    while (low <= high)
    {
        if (arr[low] >= pivot)
        {
            if (arr[high] <= pivot)
            {
                temp = arr[high];
                arr[high] = arr[low];
                arr[low] = temp;
                low++;
            }
            high--;
        }
        else if (arr[high] <= pivot)
        {
            low++;
        }
        else
        {
            low++;
            high--;
        }
    }
    if (low == high)
    {
        if (arr[low - 1] < pivot)
        {
            temp = arr[low];
        }
        else
        {
            temp = arr[low - 1];
        }
    }
    else
    {
        temp = arr[high];
    }
    arr[high] = arr[partitionI];
    arr[partitionI] = temp;
    return high;
}

void quickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int p = partition(arr, left, right);
        quickSort(arr, left, p);
        quickSort(arr, p + 1, right);
    }
}

*I get a stack overflow error when I run said "almost sorted" binary file. Any idea why this is happening? Thanks

Answer 1

If using the first value for the pivot value in quicksort, an already sorted list is the worse case, since the pivot will always be the lowest value in the partition. This can greatly increase the recursion depth. Each recursive call requires room on the stack frame (consisting of the parameters, local variables and return address). For an almost sorted list of a million numbers, your may need close to a million stack frames active at one time. That could easily exhaust the available stack space and generate your error.

You could try a different pivot algorithm to solve this, like median of three.