Pigeonhole Sort
One hole per distinct value across the range; drop each element into its hole, then walk the holes in order. Counting sort that keeps the items.
- Category
- Sorting
- Time complexity
- O(n + range)
- Space complexity
- O(range) (Stated for the holes array only. Some texts write O(n + range) to also account for the output array — both conventions are common.)
Pseudocode
make a hole per value in [min, max] drop each element in its hole walk holes in order emit items back to the array
Reference implementation
holes = [[] for _ in range(max-min+1)]
for v in a: holes[v-min].append(v)
out = [v for h in holes for v in h]