# Bucket Sort

- Create m empty buckets (Or lists) in order.
- Split the data into the m buckets
- Sort each bucket internally using for example: quick sort or merge sort
- Concatenate all sorted buckets

With the assumption that the data can be uniformly distributed into the buckets, the time complexity as below:

- step 2: O(n)
- step 3: O(m * (n/m) log (n/m)) ≈ O(n) when m is closed to n
- step 4: O(m)

So the total time complexity is O(n) When the data is too big to fit into the memory, we can use bucket sort to split the data into small file firstly.

# Counting Sort

It is just a special case of bucket sort, which the number of bucket equal to the range of input data, so we don’t need to sort in each bucket.

- Get/Change the data rang, suppose from 0 to k
- Take a count array A to store the count of each unique object -> O(n)
- Modify the count array A such that each element at each index stores the sum of previous counts -> O(k)
- Output each object i from the input sequence based on the value of A[i] followed by decreasing A[i] by 1 -> O(n)

It can be used when k is not big, and the data range can be converted to non-negative integer.

# Radix Sort

The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort/bucket sort as a subroutine to sort which needs to be stable.