Counting Sort
Count occurrences of each key, prefix-sum the counts, place each element at its final index.
Counting and Radix Sort: Counting sort, repeated keys
in[6] = 1, key 1. count[1] drops to 0, and that is its slot: out[0] = 1.
Cost
- Best
- O(n + k)
- Average
- O(n + k)
- Worst
- O(n + k)
- Space
- O(n + k)
k is the key range.
Properties
- No: Comparison based
- Yes: Stable
- No: In place
- No: Adaptive
- No: Online
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Counting and Radix Sort covers these too, in the same run.