Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Why Stable Sorting Is Important

July 15, 2011

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 Points 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 Points according to y, the result will be sorted according to y — and this fact will be true no matter how the Points 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 Points 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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video