Skip to content

6.17 Custom Comparators

Define correct comparison relations for user-defined types and non-trivial orderings — consistency requirements that sorting correctness depends on.

algorithms sorting comparators correctness

Sorting depends on a comparison relation. A custom comparator defines that relation for user-defined types and nontrivial ordering rules. The correctness of a sort relies on the comparator being consistent. When the comparator is inconsistent, the algorithm may produce incorrect output or fail to terminate.

Problem

You have elements that are not naturally ordered, or you need an order different from the default. You want to sort using a custom rule.

Comparator Contract

A comparator must define a strict weak ordering. In practical terms:

compare(a, b) < 0   means a < b
compare(a, b) = 0   means a and b are equivalent
compare(a, b) > 0   means a > b

The relation must satisfy:

  • Transitivity If a < b and b < c, then a < c

  • Consistency with equivalence If a is equivalent to b, then both must compare the same way against any c

  • Antisymmetry in practice If a < b, then b < a must be false

These properties ensure that sorting algorithms can reason about order without contradiction.

Example

Sort records by primary key age, then by name:

compare(a, b):
  if a.age < b.age: return -1
  if a.age > b.age: return 1

  if a.name < b.name: return -1
  if a.name > b.name: return 1

  return 0

This comparator defines a lexicographic order.

Key Extraction Pattern

Instead of writing a full comparator, many systems use a key function:

key(x) = (x.age, x.name)

Sorting compares keys using the default ordering. This is easier to reason about and reduces comparator complexity.

Stability Interaction

With stable sorting, custom comparators can be layered.

Example:

stable_sort by name
stable_sort by age

The final order is by age, then by name.

With an unstable sort, this pattern fails because earlier ordering is not preserved.

Comparator Cost

Sorting complexity includes comparator cost. If comparison is expensive, total runtime increases.

For example:

O(n log n) comparisons
each comparison costs O(k)
total O(k n log n)

Common sources of high cost:

  • string comparison
  • deep object comparison
  • repeated computation inside comparator

Optimization

Precompute keys when possible:

keys[i] = key(A[i])
sort pairs (keys[i], A[i])

This avoids recomputing keys during each comparison.

Another approach is decorate–sort–undecorate:

decorated = [(key(x), x) for x in A]
sort decorated
A_sorted = [x for (_, x) in decorated]

Common Pitfalls

Non-transitive comparator

a < b
b < c
but c < a

This creates cycles. Sorting algorithms assume transitivity and may behave unpredictably.

Inconsistent equality

Returning 0 for elements that are not truly equivalent can group unrelated elements and break expectations.

Stateful comparator

A comparator that depends on external state that changes during sorting leads to undefined behavior.

Floating-point issues

Comparing floating-point values requires handling special values:

NaN
+0 and -0
infinity

NaN does not compare consistently with any value, including itself. Sorting must define a policy for such values.

Reverse Order

To sort in descending order, reverse the comparator:

compare_desc(a, b) = compare(b, a)

Or negate the result when using numeric comparisons.

Partial Orders

Some domains define only partial orderings. Sorting requires a total order. Convert a partial order into a total order by adding tie-breaking rules.

Example:

primary key
secondary key
original index

This ensures every pair of elements is comparable.

Correctness

Sorting correctness depends on the comparator satisfying its contract. If the comparator is valid, the sorting algorithm guarantees:

output is ordered under comparator
output is a permutation of input

If the comparator violates its contract, no correctness guarantee holds.

Testing Comparators

To validate a comparator:

  • Test transitivity on random triples
  • Test symmetry: if a < b, then not b < a
  • Test consistency across repeated calls
  • Test edge cases such as equal keys

Implementation Notes

Prefer key extraction over raw comparator functions when possible. It simplifies reasoning and often improves performance.

Document comparator behavior explicitly, especially for edge cases and tie-breaking rules.

Keep comparators pure. Avoid side effects and dependence on mutable global state.

Takeaway

Custom comparators define the ordering relation used by sorting. Their correctness is as important as the sorting algorithm itself. A well-defined comparator ensures predictable and correct results.