What to hand in

algo with count and radix, passing go test ./..., plus a report.

1. Three sorts, one key

n = 1,000 / 10,000 / 100,000, key Rating:

n	counting	sort.SliceStable	ratio

How does the ratio change as n grows? Explain it in terms of O(n + k) and O(n log n).

2. The point where k wins

Find the smallest k at which counting sort becomes slower than sort.SliceStable at n = 10,000.

Widen an artificial key range and measure. Give the k and the k/n ratio.

3. Three levels of stability

One sentence each:

• lesson 7: what happens with an unstable sort?
• lesson 8: what happens?
• lesson 9: what happens?

Then one sentence on why it is the same property with such different consequences.

4. When a key can be converted

Counting sort needs an integer from a known range.

Name two kinds of data in your own library whose key looks unsuitable but could be converted into a suitable one. Implement and measure one of them.

(Hint: the first letter. The decade. A rating rounded to the nearest five.)

5. The decision

One paragraph: across your library's sorting, where will you use counting sort and where a comparison sort?

Go through every Item field and give a decision for each. Where the answer is "comparison", say why — and if the reason is the same for three of the fields, say that too.