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

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?

If element A `==` element B but the comparator function tells `qsort` that `B > A` then `qsort` will think there may be other elements which should be between `A` and `B` when that is not the case, and therefore perform unnecessary checks.

Technically, you can do with just less-than, because `a == b` is equivalent to `!(a < b) && !(b < a)`.

If the quicksort inner loop is written equivalent to this:

while(x[i] < pivot) i++; // less-than
while(pivot < x[j]) j--; // less-than

then you can get away with only implementing `<`.

In any case, stick to the [principle of least astonishment][1] by making it more obvious what the caller is supposed to do -- if your compare function pointer is named `compare` and the function shouldn't behave like a usual stdlib `qsort` compare delegate, then it's a bad idea.

On the other hand, if your parameter is named something like `less_than` or `isLessThan`, it should be much more obvious to the caller what is expected from the comparison function:

void sort(
const void * arr,
size_t num_items,
size_t element_size,
bool (*is_less_than)(const void*, const void*)
);


[1]:

[To see links please register here]

`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.

Based on the comment of @Matteo Italia, there is an efficiency issue in the number of comparison and you can reduce the number of comparison using the equality as `a == b` and `!(a < b) && !(b < a)` are equivalent in some cases (for example when the values are integer).

Also, in more general case (not in qsort specifically as mentioned in comments), you need it for stability of the sort function. In equality cases, if the sort wants to be stable, it should know about the equality in the comparison. You can know more about the stabilty in sorting [here][1].
Hence, **three value return is required for stable sort methods**.


[1]:

[To see links please register here]