In recent years, one of the questions I have increasingly seen in programming job interviews is about constant time sorting algorithms like do you know any O(n) sorting algorithm? how do they work? When I first encountered this question, I had no idea whether we can sort in constant time because even some of the fastest sorting algorithms like QuickSort or MergeSort take O(N log N) time for sorting on their average case. After some research, mainly by going through the classic CLRS book and this DS and Algorithms course by Tim Buchalka and Goran Lochert on Udemy, I come to know that there indeed are some constant time or linear time sorting algorithms like bucket sort, counting sort, and radix sort, which can sort an array in O(n) time but they work with only a special set of input.
