qsort unexpectedly working while using "a > b" as comparator

Question

I came across a qsort comparator function that was incorrectly using "a > b" as the comparison operation. I would expect this code to just somewhat randomly reorder the array, but it was working on my school's instructional servers (Ubuntu 12.04.4 LTS). It didn't work on my own laptop as expected, so I'm not sure what could be causing this bug.

#include <cstdio>
#include <cstdlib>

void print_arr(int* arr, size_t n) {
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int int_compar(const void *x, const void *y)
{
  int i_x = *((int*)x);
  int i_y = *((int*)y);
  return i_x > i_y;
}

int main(int argc, char *argv[])
{
  int n = (1<<4);
  int in[n];

  for(int i = 0; i < n; i++)
    in[i] = rand() % 100;

  printf("Before: ");
  print_arr(in, n);

  qsort(in, n, sizeof(int), int_compar);

  printf("After: ");
  print_arr(in, n);

  return 0;
}

My laptop:

$ ./qsort_test
Before: 7 49 73 58 30 72 44 78 23 9 40 65 92 42 87 3
After: 23 7 9 3 58 44 42 40 49 30 65 72 73 78 87 92

Ubuntu:

$ ./qsort_test
Before: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26
After: 15 21 26 27 35 49 59 62 63 77 83 86 86 90 92 93

It "works" by sheer luck; there's clearly some detail of that specific qsort implementation that happens to produce the correct result for that particular input set with that particular (broken) comparator. — Oliver Charlesworth
Ubuntu qsort() evidently does the same thing when the fcmp() return value is < 0 or 0. OP's qsort() takes a different path, maybe does the same on > 0 or 0. — chux - Reinstate Monica
The usual implementation of qsort in glibc only cares whether the comparator is <= 0. But if it falls back on quicksort, it cares whether it's < 0 instead, which won't work with your comparator. — Tavian Barnes
@Tavian Barnes yes, it's unlikely to be sheer luck that it works. Perhaps the sort implementation that works, unnecessarily swaps values that are considered equal, which will then work for the case i_x < i_y — Weather Vane

Deduplicator Deduplicator · Accepted Answer · 2014-10-28T22:31:08

You are breaking the contract for using qsort, thus invoking Undefined Behavior.
Specifically, your comparison-function is bad:

7.22.5.2 The qsort function

Synopsis
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
Description
2 The qsort function sorts an array of nmemb objects, the initial element of which is pointed to by base. The size of each object is specified by size.
3 The contents of the array are sorted into ascending order according to a comparison function pointed to by compar, which is called with two arguments that point to the objects being compared. The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.
4 If two elements compare as equal, their order in the resulting sorted array is unspecified.
Returns
5 The qsort function returns no value.

It should be more along the lines of:

int int_compar(const void *x, const void *y)
{
  int i_x = *(int*)x;
  int i_y = *(int*)y;
  return i_x > i_y - i_x < i_y;
}

Now, the comparison-function is partially functional instead of completely broken, it does indicate whether the first is bigger than the second, but does not differentiate between them being equal or the second being bigger.
Depending on how the algorithm happens to be written, that might make the algorithm see all as equal, not react to your error at all, or do something funny.
For an example, all C++ standard-library sorting algorithms are written to only use less-than for comparison.

qsort unexpectedly working while using "a > b" as comparator

1 Answers

7.22.5.2 The qsort function