Sorting algorithms like Selection sort, Bubble sort, quick sort, merge sort, etc. sort data by comparing an elements with one another. Hence, they are called comparison sorts. The best worst case time complexity that can be achieved using comparison sorts is O(NlogN). However, there is another class of sorting algorithms that actually have a better time-complexity than comparison sorts. These algorithms sort elements in O(N) time and are called linear time sorting algorithms.
You might be wondering, why not use linear sorting all the time? Well, we can achieve linear time complexity only when the data fits certain criteria. One example is that if the input data-set contains only positive numbers, the max and the min values of the data set is know (data set range is known) etc, then we can use that to device a simpler sorting algorithm. A generic data set may or may not meet this criteria and hence we cannot blindly apply linear sorting algorithms to any generic data.
Comparison sorting algorithms gives us an average time complexity of O(NlogN) for any kind of data with out any restrictions. Where as linear sorting algorithms can go very bad if the pre-conditions are not met. Thus, it is important to choose the right sorting algorithm. Counting sort and radix sort are two examples of linear sorting. We will learn about these two sorting algorithms in the next two sections.