A Novel Time and Space Complexity Efficient Variant of Counting-Sort Algorithm
Asad R. Usmani · 2019
Sorting is a well-known problem, which is most commonly discussed in Algorithms. Although, there exist many algorithms to solve the sorting problem but Counting-sort algorithm has its own importance due to its linear time-complexity, which is O(n+k) with 2n+k space-complexity. Moreover, depending upon the feasibility of input data, It is the most efficient sorting algorithm available in terms of time if holds but a significant value of k-n restricts its usage in practice due to its high memory and computational demands in case of violation. So, in this paper, we have proposed a novel variant of trivial Counting-sort algorithm, which is comparatively not only time but space efficient as well. The time and space complexity of our proposed ARU-Counting-sort algorithm is O(n+√k) and 2n+2√k respectively.