Q: Selection sort makes only n−1 swaps, fewer than any other comparison sort. Why is it still unstable?

Each swap moves an element across an arbitrary distance, hopping it past its own equals. Stability is about distance travelled, not about how many moves are made. Prism’s first selection-sort swap on random input exchanges a[0] with a[14], so whatever sat at a[0] is thrown fourteen places right, past any key it ties with in between. Insertion sort makes far more moves and stays stable precisely because every one of them is a single-position shift.

Q: Merge sort is O(n log n) just like quicksort. What does it spend that quicksort does not?

O(n) auxiliary memory — the merge needs a scratch buffer to read while it rewrites the range. A merge writes its output over the same range it is reading, so it must copy that range aside first — and at the top level that range is the whole array. Prism draws the buffer rather than describing it: on the final merge of sixteen values, the strip above the array holds all sixteen at once. That linear cost is what buys the stable, worst-case-bounded, front-to-back behaviour quicksort does not have.

Q: What does "in place" actually promise about a sort’s memory use?

Auxiliary space is O(1) or O(log n) — bounded independently of the data being sorted. In place is a statement about auxiliary space, and the accepted bar is O(1) or O(log n) — small enough that memory use does not scale with the input. Quicksort qualifies on that reading, because its only extra cost is a recursion stack of depth log n. Merge sort does not, because its buffer is linear in n, and that one difference decides which sort fits inside a tight memory budget.

Q: Quicksort is called in place, yet it can still exhaust memory on a large input. How?

The recursion stack is O(depth), and a run of bad pivots makes that depth n rather than log n. The auxiliary cost is the call stack, and its size is the recursion depth rather than a constant. Balanced splits keep that at log n, a few dozen frames even for enormous arrays, but degenerate pivots push it toward n and the process runs out. The standard defence is to recurse into the smaller side and loop on the larger, which caps the stack at log n whatever the pivots do.

Q: Heap sort sorts in place with a guaranteed O(n log n) bound. Why is it not the default library sort?

It is unstable and has poor locality, so a tuned quicksort or Timsort usually beats it in practice. Heap sort has the best guarantees on paper and loses on constants: sift-down jumps between positions i, 2i+1 and 2i+2, which defeats prefetching, and it scrambles equal-key order on the way. Libraries therefore reach for Timsort or introsort, the latter starting in quicksort and switching to heap sort only when the recursion runs too deep. That fallback is heap sort earning its keep as insurance rather than as a first choice.

Q: Can a sort be stable and in place at the same time?

Yes, but the O(n log n) constructions carry constants bad enough that libraries decline them. Insertion sort is stable and in place at O(n²), and block merge sort reaches stable, in-place O(n log n) by juggling part of the array into a movement buffer. The constants there are poor enough that real libraries take one of two easier deals instead: Timsort, which is stable and spends O(n) memory, or introsort, which is in place and gives up stability. Naming the trade and then saying which side you would take is the answer being looked for.

Q: Your language’s sort makes no stability guarantee. What is the alternative to sorting twice?

Sort once with a comparator that compares department and falls back to name on a tie. A composite comparator makes the tie-break explicit instead of relying on the algorithm to inherit it, and it does the job in one pass rather than two. It also documents the intent at the call site, which is worth something the next time somebody changes the ordering. Attaching the original index is the related trick for making an unstable sort behave stably — but as a final tie-break, after the real keys, not in place of them.

Question 1

What exactly does it mean for a sort to be stable?

Accepted Answer

Records that compare equal come out in the same relative order they went in. Stability is a promise about ties and only about ties: if two records compare equal on the sort key, the one that started earlier finishes earlier. Where every element is distinct the property is invisible, which is why it feels academic until a record has more than one field. The moment the same data is sorted twice on different keys, it becomes the whole question.

Question 2

You want employees ordered by department, and by name within each department. How does stability deliver that?

Accepted Answer

Sort by name first, then by department with a stable sort — the name order survives inside each group. Sequential sorting works from the least significant key to the most significant, so name first and department second. A stable department sort never disturbs two records that share a department, and the name ordering it inherited survives intact. Use an unstable sort for the second pass and the names come out shuffled, which is the classic silent bug.

Question 3

Which of these standard sorts is stable as it is normally written?

Accepted Answer

Merge sort, because a tie is resolved in favour of the left half’s front element. Merge sort, insertion sort and the prefix-sum form of counting sort are stable; quicksort, heap sort and selection sort are not. The dividing line is whether an element ever moves a long distance in one operation — merging and shifting move by one position, while partitioning and sifting hop. Prism’s merge sort makes the rule explicit in its comparison: `buffer[left] <= buffer[right]` takes from the left.

Question 4

Selection sort makes only n−1 swaps, fewer than any other comparison sort. Why is it still unstable?

Accepted Answer

Each swap moves an element across an arbitrary distance, hopping it past its own equals. Stability is about distance travelled, not about how many moves are made. Prism’s first selection-sort swap on random input exchanges a[0] with a[14], so whatever sat at a[0] is thrown fourteen places right, past any key it ties with in between. Insertion sort makes far more moves and stays stable precisely because every one of them is a single-position shift.

Question 5

Merge sort is O(n log n) just like quicksort. What does it spend that quicksort does not?

Accepted Answer

O(n) auxiliary memory — the merge needs a scratch buffer to read while it rewrites the range. A merge writes its output over the same range it is reading, so it must copy that range aside first — and at the top level that range is the whole array. Prism draws the buffer rather than describing it: on the final merge of sixteen values, the strip above the array holds all sixteen at once. That linear cost is what buys the stable, worst-case-bounded, front-to-back behaviour quicksort does not have.

Question 6

What does "in place" actually promise about a sort’s memory use?

Accepted Answer

Auxiliary space is O(1) or O(log n) — bounded independently of the data being sorted. In place is a statement about auxiliary space, and the accepted bar is O(1) or O(log n) — small enough that memory use does not scale with the input. Quicksort qualifies on that reading, because its only extra cost is a recursion stack of depth log n. Merge sort does not, because its buffer is linear in n, and that one difference decides which sort fits inside a tight memory budget.

Question 7

Quicksort is called in place, yet it can still exhaust memory on a large input. How?

Accepted Answer

The recursion stack is O(depth), and a run of bad pivots makes that depth n rather than log n. The auxiliary cost is the call stack, and its size is the recursion depth rather than a constant. Balanced splits keep that at log n, a few dozen frames even for enormous arrays, but degenerate pivots push it toward n and the process runs out. The standard defence is to recurse into the smaller side and loop on the larger, which caps the stack at log n whatever the pivots do.

Question 8

Heap sort sorts in place with a guaranteed O(n log n) bound. Why is it not the default library sort?

Accepted Answer

It is unstable and has poor locality, so a tuned quicksort or Timsort usually beats it in practice. Heap sort has the best guarantees on paper and loses on constants: sift-down jumps between positions i, 2i+1 and 2i+2, which defeats prefetching, and it scrambles equal-key order on the way. Libraries therefore reach for Timsort or introsort, the latter starting in quicksort and switching to heap sort only when the recursion runs too deep. That fallback is heap sort earning its keep as insurance rather than as a first choice.

Question 9

Can a sort be stable and in place at the same time?

Accepted Answer

Yes, but the O(n log n) constructions carry constants bad enough that libraries decline them. Insertion sort is stable and in place at O(n²), and block merge sort reaches stable, in-place O(n log n) by juggling part of the array into a movement buffer. The constants there are poor enough that real libraries take one of two easier deals instead: Timsort, which is stable and spends O(n) memory, or introsort, which is in place and gives up stability. Naming the trade and then saying which side you would take is the answer being looked for.

Question 10

Your language’s sort makes no stability guarantee. What is the alternative to sorting twice?

Accepted Answer

Sort once with a comparator that compares department and falls back to name on a tie. A composite comparator makes the tie-break explicit instead of relying on the algorithm to inherit it, and it does the job in one pass rather than two. It also documents the intent at the call site, which is worth something the next time somebody changes the ordering. Attaching the original index is the related trick for making an unstable sort behave stably — but as a final tie-break, after the real keys, not in place of them.

Question 11

Insertion sort shifts elements right while they are strictly greater than the key. Why strictly?

Accepted Answer

It stops at the first equal element, so the key lands after its equals and stability holds. Change `>` to `>=` and the key keeps shifting past elements it ties with, ending up in front of records that arrived earlier — a stable sort turned unstable by one character. That is how narrow the property is in practice, and how easily an optimisation can lose it. Prism draws the mechanism directly: the key is lifted out and its neighbours slide right one position at a time, never hopping.

Question 12

Counting sort is called stable, but only when written a particular way. Which way?

Accepted Answer

Turn the counts into prefix sums, then place records by scanning the input backwards. The stable form turns the counts into running totals, which tells each record its exact destination slot, then walks the input from the end so later records take the later slots. The simpler variant — read the counts and emit that many copies of each value — is the one Prism runs, and it works only because its elements are bare numbers with nothing attached. Knowing which variant you have is the difference between a working radix sort and a broken one, since radix sort depends on each digit pass being stable.

Question 13

What do JavaScript’s `Array.prototype.sort` and Python’s `list.sort` guarantee about stability?

Accepted Answer

Both must be stable — Python always has been, and JavaScript has been since ES2019. Python’s list sort has been Timsort, stable by contract, for two decades, and ES2019 made stability mandatory in JavaScript after years of engines switching algorithms above a size threshold. Java splits the difference by element type: object arrays get a stable Timsort, primitive arrays get an unstable dual-pivot quicksort. C++ makes you choose out loud, with `std::sort` unstable and `std::stable_sort` not. Knowing which of your languages promise it matters, because the multi-key idiom is silently wrong without the promise.

Question 14

Why does stability feel like an academic property right up until it suddenly is not?

Accepted Answer

It is invisible while elements are bare values, and decisive once records carry other fields. Sorting a list of numbers gives you no way to tell one 7 from another, so stability changes nothing you could observe. Sorting orders by date, where each order also carries a customer and an amount, makes the tie order a visible property of the output. The property does not become important at some size — it becomes important the moment an element has more to it than its key.

Question 15

An 80 GB file must be sorted on a machine with 8 GB of RAM. Does an in-place sort save you?

Accepted Answer

No — in place bounds the auxiliary memory, not the working set, and the data itself does not fit. In place is a promise about the extra memory a sort needs beyond its input, and it says nothing about whether that input fits. The shape that works is external merge sort: read chunks that do fit, sort each in memory, spill them as sorted runs, then merge the runs with one buffered reader each. It works because merging reads strictly front to back, which is the access pattern disks and networks are built for, and it is exactly the pattern quicksort lacks.

Question 16

Merge sort needs O(n) auxiliary space on an array. What changes when the input is a linked list?

Accepted Answer

The merge relinks nodes instead of copying them, so the extra space drops to O(1) pointers. The array buffer exists because writing output over the input would destroy cells not yet read, whereas a linked merge just moves pointers and overwrites nothing. That makes merge sort the standard choice for lists and quicksort a poor one, since partitioning wants the random access a list will not give. The recursion still costs O(log n) of stack, which is why the honest claim is constant auxiliary space rather than none.

Question 17

A merge finds the two half-fronts equal. Which one is written out, and why does the choice matter?

Accepted Answer

The left half’s, because `buffer[left] <= buffer[right]` takes left on a tie — that is the stability. Elements in the left half started earlier in the array, so taking left on a tie preserves arrival order while taking right would invert it. The whole of merge sort’s stability rests on that one `<=`. Prism says so in as many words when the top-level merge asks you to predict which front it takes.

Question 18

Explain to a non-programmer what a stable sort is and why anyone would care. Say it out loud before revealing.

Accepted Answer

Say I hand you a stack of exam papers already in alphabetical order by student name, and I ask you to reorder them by grade. When you are done, all the A papers are together, all the B papers are together, and so on. But here is the question nobody thinks to ask: inside the pile of A papers, are the names still alphabetical? If your method never disturbs two papers that got the same grade, then yes — the alphabetical order you started with is still sitting there inside each grade. That is what people mean by a stable sort. If your method throws papers around, the grades are right but the names inside each grade are in no order at all, and you have quietly destroyed work you did earlier. The reason it matters is that this is how you get two-level ordering for free: sort by name, then sort by grade, and you end up with papers grouped by grade and alphabetical within each group, having never written a rule about names and grades together. Do the second sort with a method that shuffles ties, and the names come out scrambled with no error message and no crash — just a wrong-looking list that somebody eventually notices.. The test is whether the listener can predict the output of two sorting passes without being told the rule again. A strong answer gives a concrete pair of records that tie, and shows what the two possible outcomes look like on the page.

Stability, in-place, and when they matter — every question, written out