# Why Stable Sorting Is Important

On June 29, I showed a technique for comparing aggregates in order to sort a sequence of aggregates:

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

This function implements what is usually called "dictionary order:" A `Point, p`

, is considered "less than" another `Point, q`

, if `p.x`

is less than `q.x`

, or if `p.x`

and `q.x`

are equal (which we express here by saying that `q.x < p.x`

is false) and `p.y`

is less than `q.y`

.

This function is not easy to explain — at least, not easy when you compare the explanation with the function's purpose: sorting a sequence of `Point`

s first according to `x`

and then according to `y`

. It is much easier to solve the original problem by sorting the sequence twice. The hardest part about explaining that strategy is that the sorts have to be stable and in reverse order. In other words, to sort a sequence "first according to `x`

and then according to `y`

:"

- You must first sort the sequence according to the
*less*important criterion`(y)`

, then according to the more important one`(x)`

; and - The sorts must be stable.

The first of these points may be counterintuitive. It would seem that the way to solve this problem is to establish the most important criterion first, and then to work on the subsidiary one(s). One way to correct our intuition is to realize that when we sort a sequence according to a criterion, the result will be sorted according to that criterion. This seemingly obvious statement implies that after we have sorted a sequence of `Point`

s according to `y`

, the result will be sorted according to `y`

— and this fact will be true no matter how the `Point`

s were originally sorted. In other words, whatever criterion we use to sort last will override all earlier criteria. When we sort a sequence, we are reordering the sequence in a way that overrules prior ordering whenever there is a conflict.

So, if we sort according to `y`

, and then we sort again according to `x`

, the second sort will rearrange the sequence elements according to `x`

when it must, but when there is no need to rearrange elements — that is, when `x`

values are equal — the earlier ordering according to `y`

will stay. Because later sorts override earlier ones, the most important sorting criteria must come last.

Our two requirements — use the less important criteria first, and sort stably — answer a question that students often ask about sorting: If a stable sort is one that leaves equal elements in the same order, what is the point? If the elements are equal, why do we care about the order? The reason is that only a stable sort preserves prior ordering when it can. If we did not use a stable sort, then the result of sorting according to `x`

can rearrange `Point`

s with equal `x`

values as it pleases. You can think of an unstable sort as being like an arbitrary rearrangement of the input followed by a stable sort.

Why aren't all sorts stable? Whenever we call an unstable sort, we are implying that we don't care about the order of equal elements, so we shouldn't mind if their original order is preserved. For this reason, it is harmless to replace an unstable sort by a stable sort with the same comparison function. The main reason is one of efficiency: The C++ standard specifies average performance for unstable sorting of `N log(N)`

; for stable sorting, it's `N log2(N)`

. On the other hand, for unstable sorting, the performance requirement is for the *average* execution time; for stable sorting, the requirement is for *maximum* time. The requirements are written as they are to allow the Quicksort algorithm for unstable sorting and merge sort for stable sorting.

Because of the execution-time requirements, `sort`

will usually be faster than `stable_sort`

, and substantially faster on large inputs. Moreover, Quicksort typically uses less auxiliary memory than merge sort. However, Quicksort does have the flaw that it can run extremely slowly (`O(N2)`

) on particularly unfortunate inputs. Therefore:

- If you care about the order of "equal" elements — for example, if you are sorting the same data more than once in order to combine comparison criteria — you should use
`stable_sort`

. - If you want to be sure that the sort will complete in a reasonable amount of time, you should use
`stable_sort`

. - If you want to minimize the average execution time and space, you should use
`sort`

.

If I were designing the C++ library, I would make stable sorting the default, because I prefer programs that keep their users out of trouble, even when they run slightly more slowly. However, the choice of default is not terribly important as long as programmers know that the two different sort routines exist, and when they should choose one over the other.

## Comments: