AlgoScope

Stable Sorting

algorithmbeginnerTime O(n^2)Space O(1)

Equal keys look the same to the sort, but not to you: they may carry different records. A stable sort keeps them in the order they arrived. Insertion sort is stable because it only moves a key past strictly larger ones. Selection sort is not, because a swap can jump a key over its equal twin.

5031521344

The value 5 appears 2 times. Its copies are tagged in the order they start: solid at index 0, dotted at index 2. A stable sort must finish with the tags in that same order. Run insertion sort.

Check your understanding

The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.

  1. The 5 being inserted has reached the other 5. Does it move past it?

    • Stops behind it, order kept
    • Moves past it, order flips

    Answer: Stops behind it, order kept. The loop only continues while the value before is strictly greater. Equal means stop, so the later copy stays later.

How it runs, step by step

  1. The value 5 appears 2 times. Its copies are tagged in the order they start: solid at index 0, dotted at index 2. A stable sort must finish with the tags in that same order. Run insertion sort.

    The repeated value 5 is tagged at indices 0, 2. Running insertion sort to see whether the tags keep their order.

  2. Insert 3 from index 1. It moves past 1 larger value to index 0.

    Insert 3 from index 1 to index 0.

  3. Insert 5 from index 2. 5 before it is not greater, so it stays put. It now sits right behind the other 5. The test is strictly greater, so an equal value is never passed: the tags stay in order.

    Insert 5 from index 2 to index 2. It stops behind the equal value ahead of it.

  4. Insert 1 from index 3. It moves past 3 larger values to index 0.

    Insert 1 from index 3 to index 0.

  5. Insert 4 from index 4. It moves past 2 larger values to index 2.

    Insert 4 from index 4 to index 2.

  6. Sorted in 6 swaps. The tagged copies of 5 finished in their original order: insertion sort is stable, because it never moves a key past an equal one.

    Sorted. The tagged copies are in their original order, so this run was stable.

Remember

  • Stable means equal keys keep their original relative order.
  • Insertion, bubble and merge sort are stable. Selection, quick and heap sort are not, unless you add the original index to the key.
  • It matters when you sort by one field of records that were already ordered by another.

Topics covered

Related

Where this is used

WebSortable tables on the web

Clicking a table's Author header after its Date header only leaves rows date-ordered inside each author if Array.prototype.sort is stable. JavaScript did not require that until ES2019: V8 ran insertion sort on arrays shorter than ten elements and an unstable quicksort on the rest, so the same table behaved differently once it reached ten rows. V8 switched to TimSort and the specification now demands stability.

GraphicsRadix sort on the GPU

LSD radix sort orders keys by the least significant digit, then the next, and so on up to the most significant. Each pass has to be stable or it destroys the ordering the pass before it established, so each pass is a counting sort, which preserves ties by construction. CUB's cub::DeviceRadixSort is built this way and its documentation states plainly that DeviceRadixSort is stable, and it is what large GPU sorts of particles or draw calls sit on.

Command linesort -s in GNU coreutils

sort -k2 does not keep input order for lines whose second field ties, because GNU sort falls back to comparing whole lines, its last-resort comparison. The -s flag disables that fallback so ties keep the order they had in the file. You need it whenever a pipeline sorts by one field and then by another. The -u flag disables the same fallback, which is why sort -k2 -u and sort -k2 | uniq disagree: -u calls two lines duplicates when only the key matches, while uniq compares the whole line.

Data analysisRe-sorting a DataFrame

pandas sort_values defaults to kind="quicksort", which is not stable, so sorting a frame by region after sorting it by timestamp scrambles the timestamps inside each region. Passing kind="stable" or kind="mergesort" picks a stable algorithm and the earlier ordering survives. Note that kind only applies when sorting on a single column. The default is the fast one because most sorts are single-key, and the bug only shows up on the second sort.

Why it works this way

The >= that silently reverses every tie

Change a[j - 1] > a[j] to a[j - 1] >= a[j] and the loop no longer stops when it meets an equal key: the arriving key keeps swapping until it sits in front of every twin already placed. Feed 5a 5b 5c to that version and it returns 5c 5b 5a. The keys are still in correct order, so no assertion on the sorted values catches it, and you paid an extra swap per tie to reverse them.

Where selection sort actually loses the order

Trace 5a 3 5b 1. The smallest value is the 1 at index 3, so the first swap is swap(0, 3): the 1 comes to the front and 5a is thrown to the back, past 5b. Nothing ever compared 5a with 5b; the swap reordered them as a side effect of moving something else. Any sort built on long-range swaps is exposed the same way, which is why quicksort's partition and heapsort's sift-down are unstable, while a merge, which only ever appends in order, is not.

To sort by two fields, sort by the less important one first

Sort the records by last name, then sort that result by department: the second pass leaves tied rows untouched, so the names stay ordered inside each department. Least important key first feels backwards, and it is exactly what LSD radix sort does with digits. A single comparator that checks department and falls back to name is one pass and usually faster, so prefer it when you hold both keys at once. The multi-pass form wins when the keys arrive at different times, such as a user clicking one column header and then another.

What stability costs

In a merge it is one character: when the fronts of the two runs tie, take from the left run, which is a <= rather than a < in the merge condition. That is why the merge-based sorts get it for nothing. The in-place partitioning sorts cannot, and bolting it on means packing each key with its original position so that nothing ever compares equal, which adds an integer per element and a second field to every comparison. On anything but small inputs that is a worse trade than reaching for a sort that is already stable.

Read more

Next up