Write CountingSortDemo. Read n k, then n records name key with keys in 0 … k. Sort the records by key with counting sort:
- count each key (print the counts);
- turn the counts into prefix sums (print them);
- place the records, scanning the input from right to left.
Records with equal keys must stay in their input order (stable).
For the input
7 3
Ana 2 Bo 0 Cy 3 Di 2 Ed 0 Flo 1 Gus 2
the program prints
counts: [2, 1, 3, 1]
positions: [2, 3, 6, 7]
sorted: Bo:0 Ed:0 Flo:1 Ana:2 Di:2 Gus:2 Cy:3
Steps: about n + k = 11, no comparisons between keys