When there are only a few kinds of value
Sort by counting how many of each value there are and writing them out, with no comparisons at all. About 12 minutes.
Tally, then write out
Suppose a bag of balls is coloured red, white or blue, written 0, 1 and 2, and you want them in order. You don't need to compare anything. Just tally how many of each colour there are: say four 0s, two 1s and three 2s.
Then write the answer straight from the tally: four 0s, then two 1s, then three 2s. It's like filling shelves, one shelf per value, already in order.
counts = [0] * 3
for value in [2, 0, 2]:
counts[value] += 1
# counts is [1, 0, 2]Read the first value, 1. Add one to the tally for 1.
When this works, and when it doesn't
The trick needs the possible values to be small whole numbers, so that you can afford one counter for each. For colours 0 to 2, that is three counters. For values up to a million, it would be a million counters, which is still fine for a long list.
It doesn't work for decimals, names, or values spread across billions, where the counters would be mostly empty and enormous. Then a comparison sort is the right tool.
You must sort a million whole numbers that are each between 0 and 9. Which approach does the least work?
- ACount each digit, then write them out
- BMerge sort
- CSwap neighbours until nothing changes
Show the answer
Count each digit, then write them out. Ten counters and two passes over the list beat a million times log of a million comparisons.
Sort the colours
nums is a list where every value is 0, 1 or 2 (like red, white and blue). Return the list sorted from smallest to largest.
nums = [2, 0, 2, 1, 1, 0, 2] → [0, 0, 1, 1, 2, 2, 2]
0 ≤ length ≤ 3,000 · every value is 0, 1 or 2