Unisort: an Algorithm to Sort Uniformly Distributed Numbers in O(n) Time
Radu Tudor Ionescu · International Review on Computers and Software (IRECOS) · 2018
In recent years, computer science specialists are faced with the challenge of processing massive amounts of data. To overcome this barrier, researchers have developed new techniques to process data in efficient ways. This paper aims to present an algorithm for sorting uniformly distributed numbers, called Unisort. Given a uniformly distributed array of numbers, the algorithm places the numbers into bins to obtain sorted sub-arrays. It then merges the sorted sub-arrays to obtain the final sorted array. This work demonstrates that if numbers are uniformly distributed, the algorithm is able to sort them in O(n) time. Furthermore, the algorithm can be generalized to numbers produced by any known distribution. The only requirement is to know the distribution a priori. However, in the worst case scenario, when the distribution is not known, the numbers may fall in the same bin. For the worst case, the algorithm becomes similar to merge sort. Experiments conducted to assess the performance level of the algorithm, in terms of time efficiency, show that it is faster than quicksort, heapsort and Bucket sort. The algorithm has broad applications in information technology, since almost every information system organizes data by sorting it.