Three Sorts, One Array

Algorithms argue in big-O. This bench argues in CMP.

One fixed shuffle. Three instruments. Bubble is the control — it is allowed to be wasteful so the others have something to beat.

Start — identical bars

-mode start

Mid — bubble still climbing

-mode mid → step 22 / 66

Same wall-clock step index. Bubble has already spent more compares than merge will need in total later.

Done — the meter that matters

-mode done

All three bars read 1…12. Only the comparison counters disagree — and they disagree by more than 2×.

Mini-exercise

Reverse the seed to 12…1. Re-run -mode done and watch bubble’s CMP stay 66 while quick’s partition counts move.

Challenges

1. Add insertion sort as a fourth column and compare its CMP to bubble.
2. Instrument swaps separately and show SWAP beside CMP.
3. Highlight the two indices involved in the latest comparison.
4. Race on n = 32 and photograph how bubble’s frame count explodes.
5. XCUITest: assert CMP 66 appears under -mode done.

Key Points

• Observed seed: 7 2 11 4 9 1 12 5 8 3 10 6.
• Observed mid (step 22): CMP 22 / 15 / 18.
• Observed done: CMP 66 / 32 / 28.
• Bubble is the control — same answer, more compares.
• CMP is the meter; sorted bars alone hide the cost.
• One shuffle shared across columns keeps the race fair.

Queue empty — the editorial list in lab-queue.json is cleared. Further Lab chapters need new queue entries.