stack overflow with quicksort implementation

Question

I'm trying to implement the quicksort algorithm (in C#),here's my code:

public static void sort(ref int[] A)
{
    if (A.Length==0 || A.Length==1) 
    { 
        return; 
    }
    quickSort(ref A,0,A.Length-1);
}

private static void quickSort(ref int[] A, int left, int right)
{
    if (left >= right || left < 0 || right < 0) 
        return;

    int pivot = A[left];

    int i = left - 1;
    int j = right + 1;

    while (true) 
    {
        do 
        { 
            i++; 
        } 
        while (A[i] < pivot);

        do 
        { 
            j--; 
        } 
        while (A[j] > pivot);

        if (i >= j) 
            break;

        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    quickSort(ref A,left,j);
    quickSort(ref A, j + 1, right);
}

This algorithm works fine, however something seems illogical, I chose pivot to be equal to A[left] then in the while(true) loop I wrote do{i++}while(A[i]<pivot), I now noticed that the first time it's going to increment i so A[i] will become equal to A[left] which is the pivot value, so that should mean this do while loop will stop after the first increment of i, so when I tried to add the = operator to the while so that it won't stop after the first increment: while(A[i]<=) I got a stack overflow exception (also got the stack overflow exception when I added the equal operator to the the 2nd do while: while(A[j]>=pivot)), and I can't understand why this happened, anyone can explain please?

Answer 1

This is Hoare partition scheme. The do while loops need to use < or >, not <= or >=, since they rely on finding the pivot or elements equal to the pivot in stop the loops and prevent the loops from going beyond the bounds of the range [lo, hi]. Normally the middle element is used as a pivot, such as

    int pivot = A[(left+right)/2];   // or A[left + (right-left)/2]

With the current code, the only element that can't be used for pivot is A[right], since that will lead to stack overflow (the quicksort call will end up stuck with high = low + 1).

So using pivot = A[left], the first do while stops with i == left, and the second do while stops with j <= right. If i < j, then a swap occurs, swapping the pivot to A[j] and an element <= pivot to A[i == left]. Each swap prevents the next pair of do whiles from running past the bounds [low, high], so only a check for i >= j is needed after the pair of do whiles to check for partition step done.

Choosing the middle element for pivot helps for certain data patterns such as already sorted data or reverse sorted data. Still, the first do while is going to stop on the first loop if the left element == pivot.

Note that Hoare partition scheme only splits the partition into elements <= pivot and elements >= pivot. The pivot or any element equal to the pivot can end up anywhere after a partition step. This isn't an issue as eventually the pivot or elements equal to the pivot will end up in the correct position (which may not occur until a level of recursion is reached where low == high).