aka bin sort or histogram sort
To sort an array of numbers with n possible values:
- allocate n "buckets," each corresponding to a different element value and holding a count
- for each element in the array, increment the count in the bucket corresponding to that element's value
- when you've finished, go through each successive bucket in order, writing the value assigned to that bucket as many times as indicated by the count in that bucket
Limitations:
- You need to know the maximum numer of times each value may be repeated, and each bucket needs to be able to hold that count.
- You need to know the range of possible values and have enough memory to store that many buckets.
Complexity is O(n) if the range of element values is fairly small, otherwise O(n+m), where m is the number of element values.
This algorithm is probably at its best when you have a small range of possible values which are about equally frequent in your array.
sorting algorithms