When comparing counting sort, bucket sort and radix sort, it’s important to know it’s about trade off between memory, time, and simplicity of data structure. Counting sort, bucket sort and radix sort can essentially all be considered as bucket sorting.

Radix sort: n log_r(k). Essentially radix sort performs bucket sort log_r(K) times. It can deal with larger key range (than bucket sort). r is the base here. the larger is r the better time complexity we got. but it also means more memory. remember the bucket array in radix sort is of length r (smaller than n or maximum value of K) If we use n as the base, it becomes a normal bucket sort. why? cuz now we have only one ‘digit’, so we only do one bucket sort/counting sort.

Bucket sort: is a generalization of counting sort. The number of bucket sort used is n. and range can be larger than n. thus we saved some space than in counting sort. but it loses the worse case of O(n+K). Also the data has to be uniformly distributed.

Counting sort: O(n+k) time and O(K) space

Reference:

https://www.ics.uci.edu/~eppstein/161/960123.html

http://stackoverflow.com/questions/14368392/radix-sort-vs-counting-sort-vs-bucket-sort-whats-the-difference

### Like this:

Like Loading...

*Related*