Why does the comparison function given to qsort() need to return three different values?

Question

I have read that the comparison function required by qsort() needs to have 3 outcomes:

• a negative result if val1 < val2
• 0 if val1 == val2
• a positive result if val1 > val2

As far as I know, sorting an array only requires a predicate that returns true or false. Take bubble sort for example:

int compare(int a, int b)
{
    if(a>b) return 1;
    return 0;
}
void bubbleSort(int arr[], int n) 
{
    int i, j;
    for (i = 0; i < n-1; i++)  
        for (j = 0; j < n-i-1; j++)  
            if ( compare(arr[j],arr[j+1]) ) 
                swap(&arr[j], &arr[j+1]);
}

So why does the qsort() comparison function need to have 3 possible outcomes and not 2?

Answer 1

qsort could be written using a boolean compare function instead of a three-way compare but the specification says that it takes a three-way compare function and some (not all) implementations take advantage of the three possible cases. If your compare function doesn't conform to the specification, Undefined Behaviour will result. In this case, Undefined Behaviour might include a failure to sort correctly or a buffer overrun triggered on very rare corner cases, which you might not notice until the space shuttle is returning from orbit. So don't do that.

As to why an implementation might want the three-way comparison, here is one possibility: for inputs with a lot of repeated values, quicksort can be speeded up considerably by using a three-way partition. That can be done with a two-way comparison by doing the comparison twice in opposite directions, but an implementor, knowing that a three-way comparator is required, is likely to test for equality when that's what they want to know.