Qsort

The following piece of C code shows how to sort a list of integers using qsort.

#include <stdlib.h>

// Comparison function. Receives two generic (void) pointers to the items under comparison.
int compareInts(const void* p, const void* q) {
    int x = *(const int*)p;
    int y = *(const int*)q;

    // Avoid returning x - y, which can cause undefined behaviour
    // because of signed integer overflow.
    if (x < y) {
        // Return -1 for ascending, +1 for descending order. 
        return -1;
    } else if (x > y) {
        // Return +1 for ascending, -1 for descending order.
        return 1;
    } else {
        return 0;
    }
}

// This could be more concisely written as:
int compareInts(const void* p, const void* q) {
    int x = *(const int*)p;
    int y = *(const int*)q;

    return (x > y) - (x < y);
}

// Sort an array of n integers, pointed to by a.
void sortInts(int* a, size_t n) {
    qsort(a, n, sizeof(*a), compareInts);
}

Since the comparison function of the original qsort only accepts two pointers, passing in additional parameters (e.g. producing a comparison function that compares by the two value's difference with another value) must be done using global variables. The issue was solved by the BSD and GNU Unix-like systems by introducing a qsort_r function, which allows for an additional parameter to be passed to the comparison function. The two versions of qsort_r have different argument orders. C11 Annex K defines a qsort_s essentially identical to GNU's qsort_r. The macOS and FreeBSD libcs also contain qsort_b, a variant that uses blocks, an analogue to closures, as an alternate solution to the same problem.^[8]

In C++, it is faster to use std::sort (or std::ranges::sort from C++20 and onwards). Compared to ::qsort, the templated std::sort is more type-safe since it does not require access to data items through unsafe void pointers, as ::qsort does. Also, ::qsort accesses the comparison function using a function pointer, necessitating large numbers of repeated function calls, whereas in std::sort, comparison functions may be inlined into the custom object code generated for a template instantiation. In practice, C++ code using std::sort is often considerably faster at sorting simple data like integers than equivalent C code using ::qsort.^[9]