Stable Sorting

A sort is stable if elements that compare equal keep their original relative order.

Why stability does not matter for plain numbers

Suppose we sort the array [3, 1, 3, 2]. There are two 3s. After sorting we get [1, 2, 3, 3]. But which 3 ended up first? We cannot tell, and it does not matter, because the two 3s are identical. One integer 3 is interchangeable with any other.

Stability only matters when each element carries more than the value we sort on. Think of sorting records, where each element has a key we compare on plus other data we carry along.

Cards are a good example. Suppose we sort a hand by rank, and the hand contains the seven of hearts, and the seven of clubs comes somewhere after it. Both have rank 7, so a sort can put them in either order. A stable sort keeps the seven of hearts before the seven of clubs, because that was their original order. An unstable sort might reverse their order. The two cards have the same rank, but they are not interchangeable, so we can see which order the sort produced.

Why stability matters

Stability lets you sort by more than one key, one key at a time.

Suppose you want your hand sorted by rank, and within each rank you want the suits in a fixed order, say clubs, diamonds, hearts, then spades. You can do that with two sorts. First sort the hand by suit. Then sort that same hand by rank, using a stable sort. Cards of the same rank keep the order they were already in, which was by suit. So you end up sorted by rank, and within each rank, by suit. If the rank sort were not stable, it could reorder cards of the same rank and lose the suit order that the first sort gave you.

Sort by the least important key first, then stably by the more important key. Radix sort will use that method in a later chapter.

What makes a sort stable

The comparison decides it. When two elements are equal, does the sort ever move one past the other?

Insertion sort does not. Its inner loop stops shifting as soon as it meets an element equal to the key. It uses a strict > in the condition arr[j - 1] > key, so the key is placed just after the equal elements and never before them:

while (j > 0 && arr[j - 1] > key) {  // stops at an element equal to the key
  arr[j] = arr[j - 1];
  j--;
}
arr[j] = key;

If we changed that > to a >=, the loop would shift the equal elements too, so the key would be placed in front of them. The array would still end up sorted, but the sort would no longer be stable.

Bubble sort is stable for a similar reason. It only ever swaps adjacent elements, and only when the left one is strictly greater than the right, arr[j] > arr[j + 1]. Two equal elements never satisfy that test, so they are never swapped past each other and keep their original order.

Selection sort is not stable. It places each element by swapping the chosen maximum into the last unsorted position, and that swap can move an element across several positions, past an element with an equal key. Take the hand 4♥, 3♣, 4♠, 2♦, sorted by rank. On the first pass selection sort looks for the highest card. The two fours tie, and the strict > keeps the first one, 4♥. The pass swaps it into the last position, where 2♦ was. That swap moves 4♥ behind 4♠. So the two fours started as 4♥ then 4♠, and they end up reversed, as 4♠ then 4♥.