Comparator Sort: A Pairwise Rule Must Order Every Pair

A comparator decides which of two values belongs first

Start with the array [7, 2, 4, 1, 6, 3]. The requested result is [2, 4, 6, 1, 3, 7]: every even value comes before every odd value, and values inside each group are ascending. A comparator is the rule that lets a sorting function build this order. It receives two values, called a and b, and answers whether a should come before b. It does not simply label a as preferred or not preferred on its own.

bool comesBefore(int a, int b) {
    return a % 2 == 0;
}

For example, when the sorting function asks about 2 and 4, recognizing that 2 is even does not tell you whether 2 or 4 comes first. Both values belong to the even group. The comparator must still answer their relative order inside that group.

A complete comparator resolves both groups and ties

Give each value a group rank before comparing its numeric value. An even value has rank 0, and an odd value has rank 1. Compare the group ranks first. If the ranks differ, the smaller rank comes first. If the ranks match, compare the values themselves so that the group is ascending.

value  group rank  sort key
7      1           (1, 7)
2      0           (0, 2)
4      0           (0, 4)
1      1           (1, 1)
6      0           (0, 6)
3      1           (1, 3)

The group rule places 4 before 7 because 4 has rank 0 and 7 has rank 1. The tie-break places 2 before 4 because both have rank 0 and 2 is smaller. It also places 1 before 3 because both have rank 1 and 1 is smaller. Applying these two comparisons gives the final order [2, 4, 6, 1, 3, 7].

C++ and Java encode the same ordering rule with different return values

C++ std::sort expects its comparator to return true exactly when a should come before b. The comparator below computes the group rank, compares ranks first, and uses a < b as the tie-break when both values belong to the same group.

#include <algorithm>
#include <vector>

std::vector<int> values = {7, 2, 4, 1, 6, 3};

std::sort(values.begin(), values.end(), [](int a, int b) {
    int rankA = a % 2;
    int rankB = b % 2;

    if (rankA != rankB) {
        return rankA < rankB;
    }
    return a < b;
});

Java's comparator returns a negative value when a comes before b, zero when they are equal for this ordering, and a positive value when a comes after b. A comparator-based Arrays.sort call needs Integer[] rather than int[], because the comparator works with Integer objects. Integer.compare expresses the numeric comparison safely, without risking overflow from subtraction.

import java.util.Arrays;
import java.util.Comparator;

Integer[] values = {7, 2, 4, 1, 6, 3};

Arrays.sort(values, new Comparator<Integer>() {
    @Override
    public int compare(Integer a, Integer b) {
        int rankA = a % 2;
        int rankB = b % 2;

        if (rankA != rankB) {
            return Integer.compare(rankA, rankB);
        }
        return Integer.compare(a, b);
    }
});

if (a % 2 == b % 2) {
    return ____;
}

A consistent pairwise rule produces one predictable whole-array order

The sorting function may compare values in an order chosen by its algorithm. It is not required to scan [7, 2, 4, 1, 6, 3] by comparing adjacent values from left to right. Each time it asks about a pair, the comparator applies the same two steps: compare group ranks, then compare numeric values when the ranks tie. Across the needed pairwise decisions, the even values settle as 2, 4, 6 and the odd values settle as 1, 3, 7, producing [2, 4, 6, 1, 3, 7].

Returning only whether a is even fails because the answer changes no matter which value is placed in the first position. For the pair 2 and 4, the rule returns true for comesBefore(2, 4), since 2 is even. It also returns true for comesBefore(4, 2), since 4 is even. That says both values should come first, so the sorting function receives contradictory answers about the same pair.