[TBD]Count sort, Bucket sort and Radix sort

Introduction

Count sort, Bucket sort and radix sort are not comparison based sort.

Count sort assumes that values in the long input list falls into some small range of integers. This method keeps count of each occurrence and then perform cumulative operation in order to get position of each of these values. So, it needs additional space of O(k) size where k is the range of possible values.

Bucket sort groups the values in different buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

Radix sort groups the values based on MSD/LSD. For each group, it applies same method. So, the problem is reduced to one lesser number of radix.

Complexity info

Radix Sort: O(kn) with space O(k+n) (k is the number of digits)

Bucket Sort: O(n) with space O(n)

Counting Sort: O(n) with space O(k) where each element is an integer and in the range of 0 to k-1

Bucket sort vs Merge sort

The n-way mergesort algorithm also begins by distributing the list into n sublists and sorting each one; however, the sublists created by mergesort have overlapping value ranges and so cannot be recombined by simple concatenation as in bucket sort. Instead, they must be interleaved by a merge algorithm.

Bucket sort vs Quicksort

Bucket sort with two buckets is effectively a version of quicksort where the pivot value is always selected to be the middle value of the value range. While this choice is effective for uniformly distributed inputs, other means of choosing the pivot in quicksort such as randomly selected pivots make it more resistant to clustering in the input distribution.

Reference

http://www.geeksforgeeks.org/counting-sort/

https://en.wikipedia.org/wiki/Bucket_sort

https://www.quora.com/Algorithms/What-is-the-difference-between-Radix-sort-Bucket-sort-and-Counting-sort

http://www.geeksforgeeks.org/radix-sort/

http://stackoverflow.com/questions/8017714/radix-sort-run-time