Sorting An Array in Pseudo Linear Time

RANDOLPH T. BUSHMAN

It is common knowledge that sorting an Array in the comparison model of sorting has a lower bound of O(n*log(n)), meaning that it is impossible to achieve a best case that sorts an array in a time complexity that is proportional to its size in all cases. If we enter the counting model of sorting, we enter a brand-new ball game. The time complexity when sorting an Array is typically faster, however we are now limited to only sorting integers or objects with integer keys. We also now depend on a second variable k (the range of the numerical values). One of the simplest algorithms in the counting model is what is known as Counting Sort. Counting Sort has a time and space complexity of O(n + k). This is important because it is used as a subroutine in the sorting algorithm which is presented in this paper. That sorting algorithm, Tuff Sort, can achieve a time and space complexity of O(n + k/n). A recent discovery has given the algorithm the ability to sort with both a time and space complexity of O(n + sqrt(k)). Neither one outperforms the other in all cases. These results bring the Computer Science community one step closer to sorting an Array in Linear time O(n).