Building a new sort function for a C library

摘要

Up to now, the most efficient sort function for a C library was a variant of Hoare's Quicksort (qsort, for short), which was proposed by Bentley and McIlroy in the early 1990s. Here we call this library function BM qsort. This paper introduces a library function which is based on Chen's Proportion Extend Sort (psort). This work is inspired by the fact that psort is generally faster than qsort, and in the worst case, qsort requires O(n~2) comparisons, while psort requires O(n log n). In our library function, many tricks used in BM qsort have been adopted, such as sorting a small array by an insertion sort and the handling of equal elements. Some new tricks are also proposed, however, such as the adaptive partitioning scheme. To assess more effectively the behavior of our function, the test cases are enhanced. The empirical results show that our function is robust and faster than BM qsort. On particular classes of inputs, such as 'already sorted', it is linear time.