Title: Sequence of Recursion calls
Tags: c;quicksort
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&gt;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]&gt;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.
Comment: I detect a hint of a misunderstanding here: "high is <= low". Keep in mind that `high` and `low` are *automatic variables* in both `quicksort()` and `partition()`. Each time one of these functions is called, the incoming values are copied into a new location. Changes made within a function invocation don't affect the caller's variables, even if they have the same name and even if the call is a recursive call to the same function. (Pointers can allow such modification, but you don't see any `&high` or `&low` here.)

Comment: Maybe add `void quicksort(int a[],int low,int high) { printf("qs l:%2d h:%2d >:%d\n", low, high,high>low);` and watch the results.

Comment: video explanation  : www.youtube.com/watch?v=y_G9BkAm6B8 // wikipedia page : en.wikipedia.org/wiki/Quick_sort


Here is another answer: 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:
Does the base case work?
Does quicksort correctly sort the array between low and high when high is not greater than(equal to) low?
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.

{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 3, 'ContentLicense': 'CC BY-SA 4.0', 'CreationDate': '2013:00:12/26/13', 'FavoriteCount': None, 'PostTypeId': 1, 'Tags': '<c><quicksort>', 'Title': 'Sequence of Recursion calls', 'ViewCount': 82, 'id': 20789347, 'user_AboutMe': None, 'user_AccountId': 3776878.0, 'user_DisplayName': 'user3137477', 'user_Reputation': 19.0, 'user_Views': 14.0, 'user_id': 3137477.0}}