AbstractThis paper introduces a new sorting algorithm called PROPORTION SPLIT SORT. The algorithm splits a sequence into two blocks in the ratio of 1:p-1, where p is a fixed constant, then divides them into four blocks with the median of the first block such that the maximum of the left two blocks is less than or equal to the minimum of the right two blocks. Finally, we perform the sorting of the left two blocks and the right two blocks separately. The worst case number of comparisons of this sorting algorithm is bounded by 1/log(2p/(2p-1))n log n for p > 1. In our simulation, when p=2, the average number is close to ( n log n-1.2n ), and for some p (e.g. p=16), this algorithm is faster than CLEVER QUICKSORT which is referred to as the fastest sorting algorithm.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: algorithm, partition, sort, quick sort, insertion sort