Nordic Journal of Computing Bibliography

J.-C. Chen. Proportion Split Sort. Nordic Journal of Computing, 3(3):271-279, Fall 1996.
Abstract

This 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


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database