qsort - What goes on behind the scenes? : <p>Using this simple sample, there are 6 numbers currently ordered 5,4,3,2,1,0 and will be sorted as : 0,1,2,3,4,5</p>

<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

int values[] = {5,4,3,2,1,0};
int sizeOfArray = sizeof(values)/sizeof(int);

int cmpfunc (const void * a, const void * b) 
{
    printf("Comparing %d and %d \n",*(int*)a, *(int*)b);
   return ( *(int*)a - *(int*)b );
}

int main () {
   int n;
   printf("Size of Array : %d\n", sizeOfArray);
   printf("Before sorting the list is: \n");
   for( n = 0 ; n &lt; sizeOfArray; n++ ) {
      printf("%d ", values[n]);
   }

   printf("\n");

   qsort(values, sizeOfArray, sizeof(int), cmpfunc);

   printf("\nAfter sorting the list is: \n");
   for( n = 0 ; n &lt; sizeOfArray; n++ ) {   
      printf("%d ", values[n]);
   }

   return(0);
}
</code></pre>

<p>Added to the cmpfunc function is a printf command to show the numbers being compared as each function is called. </p>

<pre><code>Size of Array : 6
Before sorting the list is: 
5 4 3 2 1 0 
Comparing 4 and 3 
Comparing 5 and 3 
Comparing 5 and 4 
Comparing 1 and 0 
Comparing 2 and 0 
Comparing 2 and 1 
Comparing 3 and 0 
Comparing 3 and 1 
Comparing 3 and 2 

After sorting the list is: 
0 1 2 3 4 5 
</code></pre>

<p>Notice the application only calls the cmpfunc 9 times. 
I would have expected this function to be called numerous times more. 
Also notice that 5 or 4 is never compared to 2 or to 1. </p>

<p>Is anyone able to explain what is going on behind the scenes which causes this routine to be so efficient?</p>
