Counting Sort

In general, you cannot achieve a greater time than $O\left(n\log n\right)$ for sorting algorithms where you need to compare the array elements. However, counting sort sorts an array in $O\left(n\right)$ time assuming every element in the array is an integer between 0…$O\left(n\right)$.

Here, we keep a bookkeeping array whose indices are the elements of the original array and the value is the frequency each element showed up in the original array.

Making this array takes $O\left(n\right)$ time. After this the sorted array can be created in $O\left(n\right)$ time using the bookkeeping array.

In this method of sorting, we don’t care about the values of the array elements but their frequency which is why we can sort in $O\left(n\right)$ time.