What to hand in

algo with dc and stable, passing go test ./..., plus a measurement report.

1. Four orders, four algorithms

n = 10,000, all four orders, all four algorithms — sixteen rows:

order	algorithm	comparisons	moves	wall

Mark the fastest in each order. Is the winner the same everywhere?

2. Where O(n log n) starts paying

In lesson 7, insertion sort beat sort.Slice on nearly-sorted data up to about n = 2,000.

Repeat with your own merge sort: at what n does it overtake your own insertion sort? Measure -order nearly and -order shuffled separately — the answers differ.

3. The quadratic returns

Confirm that QuickSortNaive on sorted input is exactly n(n−1)/2:

n	comparisons	n(n−1)/2	match?
100
1,000
5,000

4. The memory price

Merge sort needs extra space; quicksort does not.

Measure both at 100,000 items (runtime.ReadMemStats, as in lesson 4). Give the ratio in bytes per item.

When would that difference decide your choice?

5. The unmeasured sort in a real system

transit's fastest routing algorithm (Connection Scan) beats the best Dijkstra by about 76×. Its entire preparation is one sort; the source says so outright: "This sort is the algorithm's entire preprocessing step." It sorts 196,412 connections by departure time, with the trip number breaking ties — the same deterministic key as step 6.

transit never measured that sort's cost. It appears in none of its measurements.

Estimate it: 196,412 elements, O(n log n). How many comparisons? Compare with what Connection Scan saves on one query (~0.7 ms against ~53 ms).

After how many queries does the sort pay for itself? And is the 76× speedup still the right number if you count the preparation?

(This is not a criticism. It is a question nobody asked — which is why it is yours.)