qsort in C: comparison function without overflow

How to write a qsort comparison function in C: cast void pointers, return the sign, avoid a - b, and sort from INT_MIN to INT_MAX.

By
Published on

You pass qsort an array of int, then it asks for a function with two const void * parameters. The cast feels like ceremony, many tutorials answer with return a - b, and the sort seems fine. Until the array contains INT_MIN and INT_MAX.

In short

A qsort comparison function receives the addresses of two elements. For int, cast each address to const int *, read the value, then return a negative number, zero, or a positive number according to the order. Write return (left > right) - (left < right);, not left - right: that subtraction can overflow for two valid integers, which is undefined behavior in C.

What does a qsort comparator actually receive?

qsort does not know the element type. It knows the array address, element count, element size, and a function to call. Its two function arguments are therefore addresses, not the two int values themselves.

sort.c
#include <stdio.h>#include <stdlib.h>
static int compare_ints(const void *first, const void *second){    int left = *(const int *)first;    int right = *(const int *)second;
    return (left > right) - (left < right);}
int main(void){    int values[] = {7, -4, 0, 42};    size_t count = sizeof values / sizeof values[0];
    qsort(values, count, sizeof values[0], compare_ints);    for (size_t i = 0; i < count; i++)        printf("%d%c", values[i], i + 1 == count ? '\\n' : ' ');    return 0;}
Terminal
$ gcc -Wall -Wextra -Werror -g sort.c -o sort$ ./sort-4 0 7 42

The cast tells the compiler which type is at that address. The * then reads that int. After that, qsort only uses the sign of the result: negative when left goes before right, positive the other way, zero when they are equal.

  1. qsorttwo element addresses
  2. const void *first and second
  3. intleft and right
  4. sign-1, 0, or 1
One comparator call

The cast changes with the array type. For struct score, use const struct score *. For an array of strings, the elements are char *, so the arguments are pointers to those pointers: const char *const *.

Why can return left - right break a sort?

The difference between two int values can be outside the int range. INT_MIN - INT_MAX is not representable. The C standard makes the behavior undefined, so no comparison result is guaranteed.

subtraction.cAvoid
#include <limits.h>#include <stdio.h>
static int compare_by_subtraction(const void *first, const void *second){    int left = *(const int *)first;    int right = *(const int *)second;
    return left - right;}
int main(void){    int low = INT_MIN;    int high = INT_MAX;
    printf("%d\\n", compare_by_subtraction(&low, &high));    return 0;}
Terminal
$ gcc -Wall -Wextra -Werror -fsanitize=undefined -g subtraction.c -o subtraction$ ./subtractionsubtraction.c:9:17: runtime error: signed integer overflow: -2147483648 - 2147483647 cannot be represented in type 'int'1

The final 1 is a value observed in this environment, not a reliable ordering. The sanitizer found the error before the sort could be trusted.

The comparison version never subtracts the data. Each comparison yields 0 or 1, so their difference is necessarily in {-1, 0, 1}.

limits.c
#include <limits.h>#include <stdio.h>#include <stdlib.h>
static int compare_ints(const void *first, const void *second){    int left = *(const int *)first;    int right = *(const int *)second;
    return (left > right) - (left < right);}
int main(void){    int values[] = {INT_MAX, 0, INT_MIN};
    qsort(values, 3, sizeof values[0], compare_ints);    printf("%d %d %d\\n", values[0], values[1], values[2]);    return 0;}
Terminal
$ gcc -Wall -Wextra -Werror -fsanitize=undefined -g limits.c -o limits$ ./limits-2147483648 0 2147483647
C

qsort

The qsort exercise has you rebuild the mechanism with void *, an element size, and a comparator. Its tests use char, long, and structures, so an implementation that assumes every element is an int fails quickly.

Open the exercise

How do you sort structures and strings?

Compare a structure by the field that decides its order. Use the same comparison shape for an int field, then add a tie-breaker when the order must stay predictable for equal scores.

scores.c
#include <stdio.h>#include <stdlib.h>#include <string.h>
struct score {    const char *name;    int points;};
static int compare_scores(const void *first, const void *second){    const struct score *left = first;    const struct score *right = second;    int order = (left->points > right->points) - (left->points < right->points);
    if (order != 0)        return order;    return strcmp(left->name, right->name);}
int main(void){    struct score values[] = {{"Lina", 12}, {"Adam", 12}, {"Maya", 7}};    size_t count = sizeof values / sizeof values[0];
    qsort(values, count, sizeof values[0], compare_scores);    for (size_t i = 0; i < count; i++)        printf("%s: %d\\n", values[i].name, values[i].points);    return 0;}
Terminal
$ gcc -Wall -Wextra -Werror -g scores.c -o scores$ ./scoresMaya: 7Adam: 12Lina: 12

To sort strings, the array holds pointers to char. The comparator therefore receives the address of an element that is already a pointer: dereference it once to reach the char *, then call strcmp.

words.c
#include <stdio.h>#include <stdlib.h>#include <string.h>
static int compare_words(const void *first, const void *second){    const char *const *left = first;    const char *const *right = second;
    return strcmp(*left, *right);}
int main(void){    const char *words[] = {"zebra", "ant", "mango"};    size_t count = sizeof words / sizeof words[0];
    qsort(words, count, sizeof words[0], compare_words);    for (size_t i = 0; i < count; i++)        puts(words[i]);    return 0;}
Terminal
$ gcc -Wall -Wextra -Werror -g words.c -o words$ ./wordsantmangozebra

qsort does not guarantee the relative order of two elements your comparator considers equal. If that order matters, add a tie-breaker, such as the name in the example, or store the original index with each element.

To put the types back in place, read Array vs pointer in C. For function-pointer mechanics, Pointers in C explains their declaration. Signed overflow belongs to the same family as the examples in undefined behavior.

Frequently asked questions

Must a comparator return exactly -1, 0, or 1?

No. qsort only requires a negative, zero, or positive result. The two-comparison formula returns those three values and avoids overflow.

Why does return left - right seem to work?

Values that are close enough do not overflow the subtraction. The boundary case is still an invalid C program, even if the processor often produces a plausible-looking number.

Does qsort keep equal elements in their original order?

No. Their final order is unspecified. Add a second comparison when a deterministic order matters.

Should I write sizeof(int) in the qsort call?

sizeof values[0] is better: when the array type changes, its size follows without another edit. The same principle avoids copied sizes in Array vs pointer in C.

Sources

Now write it yourself.

Start learning CBrowse exercises