The lower bound for Comparison based sorting algorithm (Merge Sort, Heap Sort, Quick-Sort .. etc) is Ω(nLogn), i.e., they cannot do better than nLogn.
Counting sort is a linear time sorting algorithm that sort in O(n+k) time when elements are in the range from 1 to k.
The Radix sort algorithm is performed using the following steps...
Step 1 - Define 10 queues each representing a bucket for each digit from 0 to 9.
Step 2 - Consider the least significant digit of each number in the list which is to be sorted.
Step 3 - Insert each number into their respective queue based on the least significant digit.
Step 4 - Group all the numbers from queue 0 to queue 9 in the order they have inserted into their respective queues.
Step 5 - Repeat from step 3 based on the next least significant digit.
Step 6 - Repeat from step 2 until all the numbers are grouped based on the most significant digit.
