Understanding Strict Weak Ordering in C++ Sort Comparators¶

When using C++'s sort function with a custom comparator, one common pitfall is violating the strict weak ordering requirement. Let's explore this with a simple example.

The Problem¶

Consider sorting numbers based on their trailing zeros. Here's an incorrect implementation:

// INCORRECT implementation
sort(nums.begin(), nums.end(), [](int a, int b) {
    return countTrailingZeros(a) <= countTrailingZeros(b);
});

This seems intuitive but is wrong. When two numbers have equal trailing zeros, both comparisons return true:

vector<int> nums = {100, 200};  // both have 2 trailing zeros
// For a = 100, b = 200:
//   countTrailingZeros(100) <= countTrailingZeros(200)  // true
// For a = 200, b = 100:
//   countTrailingZeros(200) <= countTrailingZeros(100)  // also true!

This violates the strict weak ordering principle: if a compares true with b, then b must compare false with a.

The Solution¶

The correct implementation uses strict inequality:

// CORRECT implementation
sort(nums.begin(), nums.end(), [](int a, int b) {
    return countTrailingZeros(a) < countTrailingZeros(b);  // or > for descending
});

Now when elements are equal:

// For a = 100, b = 200:
//   countTrailingZeros(100) < countTrailingZeros(200)  // false
// For a = 200, b = 100:
//   countTrailingZeros(200) < countTrailingZeros(100)  // also false

This maintains the required properties: 1. Antisymmetry: if a < b is true, then b < a is false 2. Transitivity: if a < b and b < c, then a < c 3. Irreflexivity: a < a is always false

Remember: Always use strict inequalities (< or >) in sorting comparators, never non-strict ones (<= or >=).

Consequences of Incorrect Comparators¶

Using non-strict inequalities can lead to several serious issues:

Undefined Behavior: Most sorting algorithms assume valid comparators. Invalid ones can cause infinite loops or crashes.

vector<int> nums = {100, 200, 300};  // all have 2 trailing zeros
// With incorrect comparator using <=
sort(nums.begin(), nums.end(), [](int a, int b) {
    return countTrailingZeros(a) <= countTrailingZeros(b);
});
// May result in:
// - Infinite loop
// - Random ordering
// - Program crash

Compiler Warnings/Errors: Modern C++ compilers often detect this issue:
```
warning: '<=': operator may not give stable results
```

Debug Build Assertions: STL implementations often include debug assertions that will fail:

// Microsoft STL example
vector<int> v = {100, 200};
sort(v.begin(), v.end(), bad_comparator);  // Triggers _DEBUG assertion

The exact behavior depends on: - Compiler version - STL implementation - Debug vs Release build - Specific sorting algorithm used

This makes bugs particularly dangerous as they might only appear in specific environments or with certain data sets.

Competitive Programming Implications¶

On platforms like Codeforces, incorrect comparators often lead to runtime errors (RE):

// Common contest submission with incorrect comparator
void solve() {
    int n; cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    // Will likely result in Runtime Error
    sort(v.begin(), v.end(), [](int a, int b) {
        return someFunction(a) <= someFunction(b); // incorrect
    });
}

Why this is particularly problematic in contests: 1. Local testing might pass perfectly 2. Sample test cases often work fine 3. Error only appears in larger test cases 4. Time wasted debugging what seems like correct logic 5. Runtime Error without detailed error message

Always test your comparator with equal elements before submitting!