Theory

Stability in eight rows

In lesson 7, stability was a definition and one defect in selection sort. Here it has consequences.

The smallest possible example

Eight items, two artists, eight distinct ratings. Sort first by rating, then by artist:

$ algo stable
1. sorted by rating:      N/10 V/20 N/30 V/40 N/50 V/60 N/70 V/80
2a. then by artist (merge): N/10 N/30 N/50 N/70 V/20 V/40 V/60 V/80
2b. then by artist (quick): N/50 N/30 N/10 N/70 V/20 V/40 V/80 V/60

Both results are sorted by artist. Both are correct, if that is all you ask.

Now read the ratings inside each artist.

Merge sort: 10, 30, 50, 70 — ascending. The first sort's work survived.

Quicksort: 50, 30, 10, 70 — scrambled. The first sort's work is gone.

Why this matters

This is how multi-key ordering is done. You want "by artist, and within each artist by rating" — so you sort twice, from the least significant key to the most significant, and stability preserves the first one.

With an unstable sort that composition does not work. You need a single comparison covering both keys at once — more code, and new code for every combination you want.

Gotcha

An unstable sort does not report an error. It returns a correctly sorted list — by the key you asked for. The ordering it destroyed is the one you did not mention this time, so a test checking "is it sorted by artist" sees nothing wrong.