# 6.17 Custom Comparators

# 6.17 Custom Comparators

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:

```text id="c8y0k1"
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`:

```text id="0yshv2"
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:

```text id="o5m0tz"
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:

```text id="cprm0x"
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:

```text id="9jzt7s"
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:

```text id="v2q1cz"
keys[i] = key(A[i])
sort pairs (keys[i], A[i])
```

This avoids recomputing keys during each comparison.

Another approach is decorate–sort–undecorate:

```text id="s0h6gq"
decorated = [(key(x), x) for x in A]
sort decorated
A_sorted = [x for (_, x) in decorated]
```

## Common Pitfalls

**Non-transitive comparator**

```text id="n7e8gk"
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:

```text id="1x8kk6"
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:

```text id="r3kwcj"
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:

```text id="0c3k2l"
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:

```text id="sk1t2o"
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.