Pitfalls of Integer Subtraction in C qsort Callback

Using subtraction inside a C qsort comparison callback is a common shorthand for comparing two integers, but it introduces severe bugs that can corrupt sorting logic and cause undefined behavior. While expressions like return (*(int*)a - *(int*)b); appear concise, they fail when faced with integer overflow, violations of mathematical ordering properties, and edge cases inherent to two's complement representation. This article outlines the specific pitfalls of integer subtraction in comparators and presents the correct implementation patterns.

Signed Integer Overflow and Undefined Behavior

The primary risk of subtracting two signed integers in C is integer overflow. In the C standard, signed integer overflow is undefined behavior (UB). Modern optimizing compilers assume undefined behavior never happens and may optimize away necessary checks or alter execution paths unpredictably.

Even without aggressive compiler optimizations, the mathematical result wraps around on two's complement architectures. For example, consider comparing a large positive integer with a negative integer:

int a = 1000000000;
int b = -2000000000;
int result = a - b; // Mathematically 3,000,000,000, exceeding INT_MAX (typically 2,147,483,647)

Because 3,000,000,000 exceeds INT_MAX, the value wraps around to a negative number (-1,294,967,296). The comparator incorrectly returns a negative value, reporting that a is less than b, when a is actually greater.

The INT_MIN Asymmetry

In two's complement representation, the range of a signed integer is asymmetric: an \(N\)-bit integer spans from \(-2^{N-1}\) to \(2^{N-1} - 1\). For a 32-bit integer, this corresponds to:

  • INT_MIN: -2,147,483,648
  • INT_MAX: 2,147,483,647

Subtracting any positive number from INT_MIN immediately overflows. Furthermore, computing 0 - INT_MIN yields -INT_MIN, which cannot be represented as a positive signed integer, resulting in undefined behavior and producing unexpected negative values.

Violation of Strict Weak Ordering

The qsort function relies on a comparator that provides a strict weak ordering. This requires transitivity:

  • If \(A > B\) and \(B > C\), then \(A\) must be greater than \(C\).

When integer overflow occurs, this property breaks:

  • Let \(A = 1,500,000,000\)
  • Let \(B = 0\)
  • Let \(C = -1,500,000,000\)

Here:

  1. \(A - B = 1,500,000,000 > 0\) (\(A > B\))
  2. \(B - C = 1,500,000,000 > 0\) (\(B > C\))
  3. \(A - C = 3,000,000,000\), which wraps to a negative value (\(A < C\))

Because the comparator claims that \(A > B\), \(B > C\), yet \(A < C\), the sorting algorithm receives contradictory information. This can lead to incorrectly sorted arrays, degraded sorting performance (such as worst-case \(O(n^2)\) behavior), or infinite loops depending on the internal partitioning implementation of the C standard library.

The Correct Implementation

To compare two integers safely, avoid arithmetic subtraction and use relational operators instead.

Approach 1: Explicit Conditionals

This is the most readable and standard-compliant method:

int compare_ints(const void *a, const void *b) {
    int arg1 = *(const int *)a;
    int arg2 = *(const int *)b;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}

Approach 2: Branchless Comparison

If a concise single-line expression is preferred, relational operators evaluate to 1 or 0, completely avoiding arithmetic overflow:

int compare_ints(const void *a, const void *b) {
    int arg1 = *(const int *)a;
    int arg2 = *(const int *)b;

    return (arg1 > arg2) - (arg1 < arg2);
}

If arg1 > arg2, the expression evaluates to 1 - 0 = 1. If arg1 < arg2, it evaluates to 0 - 1 = -1. If they are equal, it evaluates to 0 - 0 = 0. This pattern works reliably across the entire range of integer values without risking undefined behavior.