On the adaptiveness of Quicksort

ABSTRACT

Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic-sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most programming libraries. Some sorting algorithms are adaptive, i.e., they have a complexity analysis that is better for inputs, which are nearly sorted, according to some specified measure of presortedness. Quicksort is not among these, as it uses Ω(n log n) comparisons even for sorted inputs. However, in this paper, we demonstrate empirically that the actual running time of Quicksort is adaptive with respect to the presortedness measure Inv. Differences close to a factor of two are observed between instances with low and high Inv value. We then show that for the randomized version of Quicksort, the number of element swaps performed is provably adaptive with respect to the measure Inv. More precisely, we prove that randomized Quicksort performs expected O(n(1 + log(1 + Inv/n))) element swaps, where Inv denotes the number of inversions in the input sequence. This result provides a theoretical explanation for the observed behavior and gives new insights on the behavior of Quicksort. We also give some empirical results on the adaptive behavior of Heapsort and Mergesort.

REFERENCES

• 1: Jon L. Bentley , M. Douglas McIlroy, Engineering a sort function, Software—Practice & Experience, v.23 n.11, p.1249-1265, Nov. 1993 [doi>10.1002/spe.4380231105]
• 2: Brodal, G. S. and Moruz, G. 2005. Tradeoffs between branch mispredictions and comparisons for sorting algorithms. In Proc. 9th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 3608. Springer Verlag, Berlin. 385--395.
• 3: Brodal, G. S., Fagerberg, R., and Moruz, G. 2005. Cache-aware and cache-oblivious adaptive sorting. In Proc. 32nd International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 3580. Springer Verlag, Berlin. 576--588.
• 4: Amr Elmasry, Priority Queues, Pairing, and Adaptive Sorting, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.183-194, July 08-13, 2002
• 5: Elmasry, A. 2004. Adaptive sorting with avl trees. In 3rd IFIP International Conference on Theoretical Computer Science. 307--316.
• 6: Amr Elmasry , Michael L. Fredman, Adaptive Sorting and the Information Theoretic Lower Bound, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.654-662, February 27-March 01, 2003
• 7: Elmasry, A. and Hammad, A. 2005. An empirical study for inversions-sensitive sorting algorithms. In 4th International Workshop on Experimental and Efficient Algorithms. 597--601.
• 8: Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992 [doi>10.1145/146370.146381]
• 9: Robert W. Floyd, Algorithm 245: Treesort, Communications of the ACM, v.7 n.12, p.701, Dec. 1964 [doi>10.1145/355588.365103]
• 10: Gianni Franceschini , Viliam Geffert, An In-Place Sorting with O(n log n) Comparisons and O(n) Moves, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.242, October 11-14, 2003
• 11: C. A. R. Hoare, Algorithm 63: partition, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366642]
• 12: C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
• 13: Hoare, C. A. R. 1962. Quicksort. The Computer Journal 5, 1 (April), 10--15.
• 14: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 15: Conrado Martínez , Salvador Roura, Optimal Sampling Strategies in Quicksort and Quickselect, SIAM Journal on Computing, v.31 n.3, p.683-705, 2001 [doi>10.1137/S0097539700382108]
• 16: Mehlhorn, K. 1984. Sorting and Searching. Springer Verlag, Berlin.
• 17: Alistair Moffat , Ola Petersson , Nicholas C. Wormald, Sorting and/by Merging Finger Trees, Proceedings of the Third International Symposium on Algorithms and Computation, p.499-508, December 16-18, 1992
• 18: Pagh, A., Pagh, R., and Thorup, M. 2004. On adaptive integer sorting. In 12th Annual European Symposium on Algorithms, ESA 2004. Lecture Notes in Computer Science, vol. 3221. Springer Verlag, Berlin. 556--567.
• 19: papi 2004. PAPI (Performance Application Programming Interface). Software library found at http://icl.cs.utk.edu/papi/.
• 20: Ola Petersson , Alistair Moffat, A framework for adaptive sorting, Discrete Applied Mathematics, v.59 n.2, p.153-179, May 12, 1995 [doi>10.1016/0166-218X(93)E0160-Z]
• 21: Sanders, P. and Winkel, S. 2004. Super scalar sample sort. In 12th Annual European Symposium on Algorithms, ESA 2004. Lecture Notes in Computer Science, vol. 3221. Springer Verlag, Berlin. 784--796.
• 22: Sedgewick, R. 1975. Quicksort. Ph.D. thesis, Stanford University, Stanford, CA. Stanford Computer Science Report STAN-CS-75-492.
• 23: Sedgewick, R. 1977. The analysis of quicksort programs. Acta Informatica 7, 327--355.
• 24: Robert Sedgewick, Implementing Quicksort programs, Communications of the ACM, v.21 n.10, p.847-857, Oct. 1978 [doi>10.1145/359619.359631]
• 25: Robert Sedgewick, Analysis of Shellsort and Related Algorithms, Proceedings of the Fourth Annual European Symposium on Algorithms, p.1-11, September 25-27, 1996
• 26: Seidel, R. 1992. Backwards analysis of randomized geometric algorithms. Tech. Rep. TR-92-014, International Computer Science Institute, Univeristy of Calfornia at Berkeley. February.
• 27: D. L. Shell, A high-speed sorting procedure, Communications of the ACM, v.2 n.7, p.30-32, July 1959 [doi>10.1145/368370.368387]
• 28: Williams, J. W. J. 1964. Algorithm 232: Heapsort. Communications of the ACM 7, 6, 347--348.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
Adaptive sorting, Quicksort, branch mispredictions