| Abstract: | A well-known improvement on the basic Quicksort algorithm is to sample from the subarray at each recursive stage and to use the sample median as the partition element. General sampling strategies, which allow sample size to vary as a function of subarray size, are analyzed here in terms of the total cost of comparisons required for sorting plus those required for median selection. Both this generalization and this cost measure are new to the analysis of Quicksort. A square-root strategy, which takes a sample of size Φ(√n) for a subarray of size n, is shown to be optimal over a large class of strategies. The square-root strategy has O(n1,5) worst-case cost. The exact optimal strategy for a standard implementation of Quicksort is found computationally for n below 3000. © 1995 John Wiley & Sons, Inc. |
