Novel Sorting Algorithm Based on Guessing Function
Sheng Bao, You Xiong Xu, De-shun Zheng, Zhendong Zhao · 2006
This article introduces a new sorting algorithm substituting the value of elements into a function to predict their positions approximately. We focus on building the function which is the mapping relationship between element values and their corresponding sorted locations. Applying the theory of entropy, we can demonstrate that its time complexity is from O(n) to O(nlgn). Experiments also indicate that it can run faster than Quicksort for small and medium scale data