Novel Hash-Based Radix Sorting Algorithm
Paul K. Mandal, Abhishek Verma · 2019
Sorting remains a quintessential problem in computer science; henceforth, considerable research has focused on optimizing runtime efficiency when sorting a collection of elements. Most algorithms for sorting objects are comparison-based. Bucket Sort and Radix Sort are non-comparison based sorting algorithms that can sort objects in linear time. In both cases, the corresponding array indices represent a hash for the object. Nevertheless, Radix Sort still requires an auxiliary array. In this paper, replacing Radix Sort's auxiliary array with a hash table is proposed. Use of a hash table in Radix Sort should avoid the calculations for the array and be better suited for handling objects. As with an array-based Radix sort, this hash-based approach should maintain linearity, thereby sorting objects more efficiently. Following successfully programming this novel sorting algorithm, as the number of elements increases, the runtime progresses linearly, not exponentially. Moreover, as the number of digits increases, the sorting runtime still lengthens linearly. Thus, a hash-based Radix sort is feasible and overcomes many issues associated with current sorting algorithms.