Inversion-sensitive sorting algorithms in practice

ABSTRACT

We study the performance of the most practical inversion-sensitive internal sorting algorithms. Experimental results illustrate that adaptive AVL sort consumes the fewest number of comparisons unless the number of inversions is less than 1%; in such case Splaysort consumes the fewest number of comparisons. On the other hand, the running time of Quicksort is superior unless the number of inversions is less than 1.5%; in such case Splaysort has the shortest running time. Another interesting result is that although the number of cache misses for the cache-optimal Greedysort algorithm was the least, compared to other adaptive sorting algorithms under investigation, it was outperformed by Quicksort.

REFERENCES

• 1: Adelson-Velskii, G., and Landis, E. 1962. On an information organization algorithm. Doklady Akademia Nauk SSSR, 146, 263--266.
• 2: Brodal, G., Fagerberg, R., and Moruz, G. 2005. On the adaptiveness of Quicksort. Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, Vancouver, B.C., Canada, January 22, pp. 130--140, SIAM.
• 3: Brodal, G., Fagerberg, R., and Moruz, G. 2005. Cache-aware and cache-oblivious adaptive sorting. Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lisboa, Portugal, July 11--15, Lecture Notes on Computer Science 3580, pp. 576--588, Springer Verlag.
• 4: Richard Cole, On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof, SIAM Journal on Computing, v.30 n.1, p.44-85, 2000 [doi>10.1137/S009753979732699X]
• 5: Curtis R. Cook , Do Jin Kim, Best sorting algorithm for nearly sorted lists, Communications of the ACM, v.23 n.11, p.620-624, Nov. 1980 [doi>10.1145/359024.359026]
• 6: Dromey, P. 1984. Exploiting partial order with Quicksort. Software: Practice and Experience, 14, 509--518.
• 7: Elmasry, A. 2004. Adaptive sorting with AVL trees. 18th IFIP World Computer Congress, Proceedings of the 3rd International Conference on Theoretical Computer Science, Toulouse, France, August 23--26, pp. 315--324.
• 8: Amr Elmasry , Claus Jensen , Jyrki Katajainen, Multipartite priority queues, ACM Transactions on Algorithms (TALG), v.5 n.1, p.1-19, November 2008 [doi>10.1145/1435375.1435389]
• 9: Elmasry, A., Jensen, C., and Katajainen, J. 2004. A framework for speeding up priority queue operations. CPH STL TR 2004-3, Department of Computing, University of Copenhagen.
• 10: 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
• 11: Amr Elmasry , Michael L. Fredman, Adaptive sorting: an information theoretic perspective, Acta Informatica, v.45 n.1, p.33-42, January 2008 [doi>10.1007/s00236-007-0061-0]
• 12: 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]
• 13: Gaston H Gonnet , J Ian Munro, Heaps on heaps, SIAM Journal on Computing, v.15 n.4, p.964-971, Nov. 1986 [doi>10.1137/0215068]
• 14: Leo J. Guibas , Edward M. McCreight , Michael F. Plass , Janet R. Roberts, A new representation for linear lists, Proceedings of the ninth annual ACM symposium on Theory of computing, p.49-60, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803395]
• 15: C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
• 16: 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
• 17: Christos Levcopoulos , Ola Petersson, Exploiting few inversions when sorting: sequential and parallel algorithms, Theoretical Computer Science, v.163 n.1-2, p.211-238, Aug. 30, 1996 [doi>10.1016/0304-3975(95)00256-1]
• 18: Christos Levcopoulos , Ola Petersson, Adaptive heapsort, Journal of Algorithms, v.14 n.3, p.395-413, May 1993 [doi>10.1006/jagm.1993.1021]
• 19: Christos Levcopoulos , Ola Petersson, Splitsort—an adaptive sorting algorithm, Information Processing Letters, v.39 n.4, p.205-211, Aug. 30, 1991 [doi>10.1016/0020-0190(91)90181-G]
• 20: Mannila, H. 1985. Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers, C-34, 318--325.
• 21: Kurt Mehlhorn, Sorting Presorted Files, Proceedings of the 4th GI-Conference on Theoretical Computer Science, p.199-212, March 26-28, 1979
• 22: Alistair Moffat , Gary Eddy , Ola Petersson, Splaysort: fast, versatile, practical, Software—Practice & Experience, v.26 n.7, p.781-797, July 1996 [doi>10.1002/(SICI)1097-024X(199607)26:7<781::AID-SPE35>3.3.CO;2-2]
• 23: Moffat, A. and Petersson, O. 1992. An overview of adaptive sorting. Australian Computer Journal, 24, 70--77.
• 24: Moffat, A., Petersson, O., and Wormald, N. 1998. A tree-based Mergesort. Acta Informatica, 35(9), 775--793.
• 25: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 26: Jean Vuillemin, A unifying look at data structures, Communications of the ACM, v.23 n.4, p.229-239, April 1980 [doi>10.1145/358841.358852]
• 27: Roger L. Wainwright, A class of sorting algorithms based on Quicksort, Communications of the ACM, v.28 n.4, p.396-402, April 1985 [doi>10.1145/3341.3348]

INDEX TERMS

Primary Classification:
  E. Data
  E.0 GENERAL

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
  E.2 DATA STORAGE REPRESENTATIONS
  E.5 FILES

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
Adaptive sorting, Inversions