Stable Sorting Algorithms

What does it mean for a sorting algorithm to be "stable"?

A sorting algorithm is stable if it preserves the order of duplicate keys.

OK, fine, but why should this be important? Well, the question of "stability" in a sorting algorithm arises when we wish to sort the same data more than once according to different keys.

Sometimes data items have multiple keys. For example, perhaps a (unique) primary key such as a social insurance number, or a student identification number, and one or more secondary keys, such as city of residence, or lab section. And we may very well want to sort such data according to more than one of the keys. The trouble is, if we sort the same data according to one key, and then according to a second key, the second key may destroy the ordering achieved by the first sort. But this will not happen if our second sort is a stable sort.

Example

Suppose, for example, that we have a file containing a list of computing science students who are enrolled in several different lab sections:

Dave  A
Alice B
Ken   A
Eric  B
Carol A

If we sort these students alphabetically using their names as the key, then it is very unlikely that they will be grouped nicely into lab sections as well:

Alice B
Carol A
Dave  A
Eric  B
Ken   A

So, we might like to sort again, using the lab section as a key, so that we have all the students in lab section A together, all the students in lab section B together, and so on. If we now do that, we might wind up with this:

Ken   A
Carol A
Dave  A
Eric  B
Alice B

And, of course, we would have liked the students in lab section A to still be in alphabetical order, as well as those in lab section B, but that did not happen. The reason it did not was that the sort we used the second time around was not stable.

If we had used a stable sort, then we would have obtained this instead:

Carol A
Dave  A
Ken   A
Alice B
Eric  B

Some particular sorts: are they stable?

We make the following observations, without proof, about some common sorting algorithms:

• InsertionSort and MergeSort are stable.
• SelectionSort is not inherently stable, but may be coded in such a way that it is stable. [See Knuth, The Art Of Computer Programming, Vol. 3, Sorting and Searching, Second Ed., pp. 138-139.]
• The stability of QuickSort depends on the stability of its partition routine. That is, QuickSort is stable if it is using a stable Partition algorithm.
• ShellSort is not stable and it is not easy to make is so, since adjacent values will appear on different sublists on early passes and may be moved in different directions.
• HeapSort is inherently unstable.

The STL stable_sort Algorithm

If you have data values in an STL container that provides random access iterators (vector or deque) and you wish to sort those values with a stable sort, the STL provides the stable_sort algorithm. Thus

stable_sort(v.begin(), v.end());