Lesson · Sorting and Selection · The four promises

What a Sort Must Promise

Order is the least of what a sort is asked for. Three further promises are separate from it and from each other: whether equal keys keep the order they arrived in, whether the extra memory is constant, and whether nearly sorted input is cheaper. None of the three follows from a complexity class, and the first of them is what lets a two-key sort be done as two one-key passes.

Open the interactive lesson Practice

stable equal keys leave in the order they arrived in place Θ(1) extra memory, the input aside adaptive cheaper on input that is already nearly sorted comparison asks only whether a ≤ b; key-based reads the key itself two keys by stable passes: the MINOR key first, then the major

Four promises, and the order two stable passes go in

Core ideas

What this lesson establishes

One hard idea: stability. The other two promises are easy to state and are here because they are routinely confused with stability and with each other.

Stability is a claim about equal keys only

A sort is stable when two records with equal keys come out in the order they went in. Tag every record with the position it started in and the property becomes visible: after a stable sort the tags inside each run of equal keys still ascend. On the list 7 3 7 1 9 3 5 1 insertion sort and merge sort leave every such run alone; selection sort leaves two pairs reversed, because the long-range swap that puts the minimum in place jumps one equal key over its twin.

In place and adaptive are different promises again

In place means the extra memory is Θ(1), the input array aside — merge sort's standard form needs Θ(n) and is not. Adaptive means already-ordered input costs less: insertion sort is Θ(n) on sorted input and Θ(n²) on reversed, and heapsort is Θ(n log n) on both. Each promise is independent of the others and of the complexity class.

A stable sort composes, and that is what it is for

To order records by a major key with ties broken by a minor key, sort on the minor key and then on the major, both passes stable. The second pass puts the major keys in order; inside each run of equal major keys it changes nothing, so the minor order the first pass established survives. Run the passes the other way and the second pass, which orders by minor key across the whole list, destroys the major order the first one built.

The material

Four promises, and which of them a complexity class implies

The definitions, the counterexample that settles a stability question, and why the least significant key is sorted first.

Definition · Stable sort

A sorting algorithm is stable if, whenever two input records have equal keys, the one that appeared earlier in the input also appears earlier in the output. The property is about the algorithm, for every input, not about one run of it.

Equal keys are the only records the definition talks about. A sort that gets the order of unequal keys wrong is not unstable; it is broken. So stability can only be observed on a list with repeats, and it is observed by carrying something the key does not determine — here the input position, called a tag.

Example · Selection sort caught on eight keys

Tag the list 7 3 7 1 9 3 5 1 by position, so the records are 7#1 3#2 7#3 1#4 9#5 3#6 5#7 1#8. Insertion sort returns 1#4 1#8 3#2 3#6 5#7 7#1 7#3 9#5 and merge sort returns the same. Selection sort returns 1#4 1#8 3#6 3#2 5#7 7#3 7#1 9#5: the threes and the sevens have each come out reversed. Two pairs out of input order, and the question is settled.

That asymmetry is worth being explicit about. One reordered pair refutes stability, because stability is a claim about every input and a counterexample is enough to kill one. Zero reordered pairs on one list establishes nothing at all: there are 8! = 40 320 lists of that length and this was one. Stability is proved from the algorithm — insertion sort never moves an element past an equal one, and merge sort's merge takes from the left run when the heads are equal — never from a measurement.

Definition · In place, and adaptive

An algorithm sorts in place if it uses Θ(1) memory beyond the array it is given. It is adaptive if its cost falls as its input gets closer to sorted, measured in whatever way the analysis names: number of inversions, or number of already ordered runs.

These two cut across stability and across the complexity class. Merge sort is stable, not in place, not adaptive in its standard form. Heapsort is in place, not stable, not adaptive. Insertion sort is stable, in place and adaptive, and quadratic. Nothing in Θ(n log n) implies any of the three, which is why the promise a situation needs has to be named before an algorithm is chosen.

The fourth promise is about what the algorithm is allowed to look at

A comparison sort may only ask, of two keys, whether one is at most the other. Every sort above is one. Discrete Mathematics' “Searching and Sorting” proves that no such algorithm can sort every array of n keys in fewer than ⌈log₂ n!⌉ comparisons, and that bound is cited throughout this course and reproved nowhere in it. A sort that reads the key itself — its digits, its value as an array index — is outside the bound rather than better than it, which is what “Counting Sort” is about.

Theorem · Two stable passes sort on two keys

Let a list be sorted by a stable pass on the minor key and then by a stable pass on the major key. The result is in increasing order of major key, and within each run of equal major keys, in increasing order of minor key.

The second pass orders the major keys, which gives the first claim.

Take two records with equal major keys. The second pass is stable, so it leaves them in the order it found them, which is the order the first pass left them in. The first pass ordered the whole list by minor key, so of those two the smaller minor key came first. Both claims hold, and the only property of the second pass that was used is its stability.

□

Read that proof backwards and the misconception dissolves. If the major pass runs first, the minor pass afterwards is the one ordering the whole list, and what survives inside its ties is the major order — so the output is sorted by minor key, with major keys as a tie-break. That is a correct sort of a different thing. The lab runs both orders on the same eight records and prints the two sequences.

This composition is not a curiosity: it is the whole correctness argument of radix sort, which is d stable passes, one per digit, least significant first. “Radix Sort” makes each pass unstable on demand and lets the composition fall apart in front of you.

Interactive

Stability is a promise about equal keys

Tag every record with where it started, then watch which sorts keep the order

Choose the list and the algorithm

Every record carries the position it was typed in, so a reordering of equal keys is seen rather than claimed. The lower panel sorts eight two-key records by two stable passes, in both orders, and prints both results.

Keys (equal keys are the interesting ones)

Algorithm

Two-key records, written major:minor

Comparisons made—

Elements moved—

Pairs out of input order—

Stable on this list—

A tag is the position a record started in. After a stable sort the tags inside each run of equal keys still ascend; after an unstable one they do not. The second list is sorted on two keys by two stable passes, in both orders.

Method

Choosing a sort, rather than recalling one

The promises come before the algorithm, and the memory limit is usually what decides.

Name the promises the situation needs

Are there equal keys whose input order carries information? Is there room for another n records? Is the input usually nearly sorted already? Each answer rules algorithms out, and none of them is the question of which sort is fastest.

Tag the records before you sort them

Attach the input position to every record. Without a tag, a reordering of equal keys is invisible: the keys come out in the same sequence either way. With one, the output is its own evidence.

Read a violation as a refutation, and zero as nothing

One pair of equal keys out of input order proves the algorithm is not stable. No such pair proves nothing about the algorithm: it is one list. If you want stability, take it from the algorithm's structure, which the lab's hint states for the two sorts that have it.

For two keys, sort on the least significant first

Then each later pass has only to order its own key, because it leaves its own ties alone. Write down which pass you intend to be stable; if a pass is not, the composition has no argument behind it.

Promises, and what settles them

Score 0 / 0

Choose the answer you can justify.

Eight records, two keys, and the two pass orders

The records are written major:minor, and they are the eight the lab loads. The aim is increasing major key, with ties broken by increasing minor key.

as typed 3:70 1:40 3:20 2:90 1:10 3:50 2:30 1:60 the order that works pass 1, stable on the MINOR key 1:10 3:20 2:30 1:40 3:50 1:60 3:70 2:90 pass 2, stable on the major key 1:10 1:40 1:60 2:30 2:90 3:20 3:50 3:70 ✓ the order that does not pass 1, stable on the MAJOR key 1:40 1:10 1:60 2:90 2:30 3:70 3:20 3:50 pass 2, stable on the minor key 1:10 3:20 2:30 1:40 3:50 1:60 3:70 2:90 ✗ the second sequence is sorted by minor key alone: 10 < 20 < 30 < 40 < 50 < 60 < 70 < 90, and the major keys 1 3 2 1 3 1 3 2 are in no order at all

Look at what each pass is responsible for. In the working order, pass 2 is the last word on the major key and pass 1 survives only inside pass 2's ties — which it does exactly because pass 2 is stable. In the other order, pass 2 is the last word on the minor key, so that is what the output is sorted by.

The lab's third table row reports whether the two orders happened to agree. On these records they do not. On a list where every major key is distinct they would, and that agreement would be a fact about the list rather than permission to choose the order freely.

For a faded rehearsal, add the record 2:10 to the end of the list and predict both outputs before running them. The supplied first move is this: 2:10 has the smallest minor key on the list, so in the working order it starts the pass-1 sequence — say where it ends up after pass 2, and then where it ends up under the other order, and check both in the lab.

Common mistakes

Reading stability off the complexity classTwo sorts in the same class need not agree about anything except the growth of their worst-case comparison count. Merge sort and heapsort are both Θ(n log n); one is stable, one is in place, and neither is both. The class is a statement about a count, and stability is a statement about where equal keys end up.

Sorting by the primary key firstIt feels like the important key should be settled first, and it is exactly backwards: the last pass is the one whose order survives across the whole list, so the primary key must be sorted last. The lab runs both orders on the same records, and the wrong one comes out ordered by the key nobody asked to order by.

Taking zero violations as a proof of stabilityThe lab says “no reordering seen” rather than “stable” for a reason. A list on which every sort happens to be stable teaches nothing, and the first list tried when this panel was built was one of those. Separate an equal pair with a smaller key and try again, and take the actual claim from the algorithm.

Check your understanding

✓

Finish when you can say which promise a situation needs before you name a sort.

You should be able to tag a record list, read a stability violation off the output, say why one violation settles the question and zero does not, and order a two-key sort's passes with a reason rather than a preference.

Note: The next four lessons are about one algorithm and one that stands beside it. “Partitioning” takes the single pass quicksort is built from, and it is worth noticing on the way that the pass is where quicksort's instability comes from: a swap moves an element across the array, past whatever equal keys lie between.