Ordering

Sorting and Ordering

Synopsis

Many algorithms in the C++ standard require the use of a set defined with a strict weak ordering in order to use both std::sort and std::stable_sort. This is contrary to the Rust standard library, which uses the trait Cmp, which instead requires a total ordering. I’ll be discussing these two concepts and how it relates to floating point numbers, and how the sorting of floats are actually undefined behavior when there is a possibility of NaN.

Strict Weak Ordering

Strict weak orderings are the intersection between two related concepts, a strict ordering, and a weak ordering.

Strict Ordering: A strict ordering comes from the phrase strict partial order. This is a partial ordering defined as a partial order with relation $\lt$. This is opposed to a strong partial order, which defines a relationship $\leq$. This is of course a simplification, but it can help with the general concept.

Weak Ordering: A weak ordering, as opposed to a total ordering, is an ordering which members of a set can be “tied” with one another.

Combining these two (weak) definitions, we can create a formalization for the Strict Weak Ordering. A Strict Weak Ordering on a set $S$ is a strict partial order $\lt$ with all four of the following properties:

  1. Irreflexivity: $\forall x \in S$, $x \lt x$ is false
  2. Transitivity: $\forall x,y,z \in S$, $(x \lt y) \land (y \lt z) \rightarrow (x \lt z)$
  3. Asymmetry: $\forall x,y \in S$, $(x \lt y) \rightarrow \neg (y \lt x)$
  4. Transitivity of Incomparability: $\forall x,y,z \in S$, $\text{incomp}(x,y) \land \text{incomp}(y,z) \rightarrow \text{incomp}(x,z)$

Where $\text{incomp}: S \rightarrow \{\text{True}, \text{False}\}$ is a boolean relationship that defines whether a member of set $S$ is incomparable with another. It is defined as the following:

\[ \text{incomp}(x,y) = \neg(x \lt y) \land \neg(y \lt x) \]

These axioms look very familiar, almost scarily familiar. Technically, the real numbers follow a well defined strict weak ordering. The first three axioms feel obvious to anybody who is thinking of a simple less than symbol, while the fourth axiom can cause someone to have to think twice about what it means.

In fact, the first three axioms, are really not necessary. Axiom #1 is a basic tenet of the partial ordering, but is also a result of Axiom #3.

Axiom #3: $\forall x,y \in S$, $(x \lt y) \rightarrow \neg (y \lt x)$

Axiom #1: $\forall x \in S$, $x \lt x$ is false

Thorem: If Axiom #3 is true for a partially ordered set $S$, then Axiom #1 is true as well

Proof: Replacing y with x, we get the statement: if x is ordered before x, then x cannot be ordered before x. This is a clear parodox.

Floating Point Ordering

A good example for this will include floating point operations, which should be used with caution. The IEEE 754 Document specifies that four mutually exclusive predicates are available between any two floating point values.

  • less than
  • equal to
  • greater than
  • unordered

A few rules for comparison include

  • All NaN values shall compare as “unordered” with anything (including itself)
  • Comparions shall ignore the sign on 0 (-0.0 and +0.0 are effectively equivalent)
  • Infinities of the same sign are equivalent
  • All unordered operations should be false for all of $\{ <, \leq, =, \geq, > \}$

So the question persists, is this a Strict Weak Ordering? We already know the answer but let’s go into detail to see the predicates broken.

  1. Irreflixivity: $\forall x \in S$, $\neg (x \lt x)$. This holds true
  2. Transitivity: $\forall x,y,z \in S$, $(x \lt y) \land (y \lt z) \rightarrow (x \lt z)$. This holds true
  3. Asymmetry: $\forall x,y \in S$, $(x \lt y) \rightarrow \neg (y \lt x)$. This holds true
  4. Transitivity of Incomparability: $\forall x,y,z \in S$, $\text{incomp}(x,y) \land \text{incomp}(y,z) \rightarrow \text{incomp}(x,z)$. This is broken

Let’s look at an example of how the fourth predicate is broken. As you can probably assume, it has something to do with the way NaN is handled. Because NaN is incomparable with everything, $\forall a \in S, \neg \text{incomp}(NaN,a)$ will be true. Substituting x and y in in the predicate with any two values where x and y are comparable result in $\text{incomp}(x, NaN) \land \text{incomp}(NaN, z) \rightarrow \text{incomp}(x, z)$ which is clearly false.

Sorting and Ordering

Quicksort cannot be correctly implemented for an algebra that does not have a strict weak ordering. More generally, sorting cannot be done at all for such an algebra.

# 1. Unordered list, choosing NaN as a pivot point
| -3  | NaN |  5  | -7  |
         ^
# 2. Partition based on x < NaN (all turn out to be false)
| NaN | -3  |  5  | -7  |

# 3. Complete Sorting on elements [1, 4)
| NaN | -7  | -3  |  5  |

Not bad, we placed a NaN all the way at the beginning, this doesn’t seem too illogical.

Now let’s choose a different pivot point.

# 1. Unordered list, choosing 5 as a pivot point
| -3  | NaN |  5  | -7  |
               ^
# 2. Partition based on x < 5, (-3 and -7 evaluate to true, NaN evaluates to false)
| -3  | -7  |  5   | NaN |

# 3. Complete Sorting on elements [0, 2)
| -7  | -3  |  5  | NaN |

So given a change in pivot point, we get a completely different location for the NaN. This is expected, because of the fact that it is incomparable. We should have no predictions on where such a group should end up.

Language Considerations

Weak Ordering in C++

C++20 introduces the compare library that provides support for strict weak orderings of floating point types. The ordering chosen by the standard seems to be to place all -NaN types as ordered before everything else, and all +NaN as ordered after everything else. This includes their respective infinities.

Total Ordering in Rust

Rust 1.62.0 provides the f64::total_cmp() function to provide an ordering a bit different from C++20. It orders negative quiet NaN before negative signalling NaN. Ditto and opposite for positive values.

Conclusion

When defining an algebra in a programming language, make sure to be specific on what exactly a comparison function will provide. Cases where a strict weak ordering is not possible or plausible include an interval type, where one interval can strictly be ordered before another if its end time is before its start time, but is incomparable for cases where intervals intersect. As you can guess, this ordering is not a strict weak ordering, and therefore cannot be used in a sorting algorithm.

Everybody who does mathematical programming should ideally already know the dangers of floating points. Depending on the situation, make sure to take great care of exceptions to general rules, including infinities, NaN’s both quiet and signalling, and the effects of positive and negative zeros.