Sequence of Recursion calls

Question

This will be dumb question, but I am having trouble to understand the sequence in which the recursion is called. For example in the quickSort algorithm, can somebody explain more detailed how it works. I will post the algorithm:

void quicksort(int a[],int low,int high)
{
    int pivot;
    if(high>low)
    {
        pivot=partition(a,low,high);
        quicksort(a,low,pivot-1);
        quicksort(a,pivot+1,high);
    }
}

int partition(int a[],int low,int high)
{
    int left,right;
    int pivot_item;
    int pivot=low;
    left=low;
    pivot_item=a[low];
    right=high;
    while(left<right)
    {
        while(a[left]<=pivot_item){
            left++;
        }
        while(a[right]>pivot_item){
            right--;
        }
        if(left<right){
            swap(a,left,right);
        }
    }
    a[low]=a[right];
    a[right]=pivot_item;
    return right;
}

int main()
{

    a[10]={5,1,13,14,7,6,19,10,9,23};
    int i;
    printf("before\n");
    for(i=0;i<10;i++)
    {
        printf("%i,",a[i]);
    }
    quicksort(a,0,10);
    printf("\n");
    printf("After sort:\n");
    for(i=0;i<10;i++)
    {
        printf("%i,",a[i]);
    }

    return 0;
}

So it call the function with the array a, low is 0, high is 10 and then the variable is assigned some value from the partition function ,then call quicksort again with high being pivot-1 this time and it continues until high is <= low ,this is where the confusion is coming for me, how is the second call to quicksort excecuted since high is becoming equal to low and the if executes to false I think.

Answer 1

The whole point of recursion is so that you don't even have to think about the whole sequence of calls that the method takes. you only have to think of the recursive relationship.

The questions that you should ask are:

1. Does the base case work?

   • Does quicksort correctly sort the array between low and high when high is not greater than(equal to) low?

2. Does the recursive relationship work?

   • Does quicksort correctly sort the array between low and high, if you assume that your other calls to quicksort work correctly?
   • You don't actually have to think about what path that they take. Just assume, on faith, for now, that quicksort(a,low,pivot-1); correctly sorts array a between low and pivot - 1. It might help you to think of it as a call to a completely different function, that completely sorts the array.

If both of those works, than your recursive function should work. This goes for all recursive functions.