# Putting Things In Order

**sort**.

Last week, I gave an example of a function that should never be passed as an argument to **sort**:

struct Point { int x, y; }; bool compare(const Point& p, const Point& q) { return p.x < q.x && p.y < q.y; }

One reader took me to task for naming this function **compare**, and another commented more generally about how to teach sorting, merging, and recursion. What surprised me is that no one asked what was wrong with this function. I can think of two possible reasons for this phenomenon:

- What's wrong with this function is so obvious that no one thought it worth mentioning.
- I didn't make it clear enough that this code was broken.

To help me decide which of these cases applies (or, for that matter, whether there's a third possibility that I've missed), I want to talk about what you have to do if you want to write a comparison function to pass to **sort**.

Obviously, such a function should make it possible for **sort** to sort its input. It doesn't actually have to be a less-than comparison; in fact, one common way to use **sort** is to pass it a greater-than comparison, which causes **sort** to sort its input into *decreasing* order. However, the function does have to be able to "compare" elements in a way that lets **sort** put them in order.

The most fundamental requirement of such a function is consistency. In particular, **sort** should never be able to determine that **a** must come before **b** in the output or that **a** must come after **b**. We can express this requirement by saying that the comparison function must be:

: If*Antisymmetric***compare(a, b)**is true,**compare(b, a)**must be false. By implication,**compare(a, a)**must always be false for any value of**a**.: If*Transitive***compare(a, b)**and**compare(b, c)**are both true,**compare(a, c)**must also be true.

These two requirements are enough to ensure that comparison is internally consistent. However, by themselves, they are not enough.

To see why, consider what might happen when we compare two values **a** and **b**. There are three possibilities:

**compare(a, b)**is true, in which case**compare(b, a)**must be false.**compare(b, a)**is true, in which case**compare(a, b)**must be false.- Both
**compare(a, b)**and**compare(b, a)**are false.

Less formally, the three cases are:

**a**must come before**b**in the output.**b**must come before**a**in the output.**a**and**b**can appear in either order.

For consistency, then, we have an additional requirement, which we might describe as follows:

- If both
**compare(a, b)**and**compare(b, a)**are false, we will say that**a**and**b**are*unordered*. - If
**a**and**b**are unordered, and**b**and**c**are also unordered, then**a**and**c**are unordered. In other words, the notion of "unordered" is transitive.

If you're mathematically inclined (as I imagine that most readers are who have gotten this far), you will see that "unordered" is reflexive (**a** and **a** are always unordered because **compare(a, a)** is always false) and symmetric (because "and" is commutative), and therefore that this requirement makes "unordered" an equivalence relation.

If your eyes have glazed over, you might start reading again here, because I have an interesting example for you. I used to program in APL, which, among other interesting features, tried to make floating-point computation a little more user-friendly by treating numbers as equal if they were close enough together. In APL, you could divide 1 by 10 and be confident that the result would be equal to 0.1.

As a result of this attempted kindness, it was possible to create three numbers, which I'll call **A**, **B**, and **C**, with the following characteristics:

**A**is equal to**B****B**is equal to**C****A**is less than**C**

It is precisely this kind of inconsistency that the C++ requirements on comparison functions is intended to prevent.

If you really want to understand the rules for comparison functions, here are two exercises:

- Find numbers
**A**,**B**, and**C**with the characteristics I mentioned. - Explain why the
**compare**function I showed at the beginning of this article is wrong.

I'll give the solutions to these exercises next week.