A survey of adaptive sorting algorithms

ABSTRACT

The design and analysis of adaptive sorting algorithms has made important contributions to both theory and practice. The main contributions from the theoretical point of view are: the description of the complexity of a sorting algorithm not only in terms of the size of a problem instance but also in terms of the disorder of the given problem instance; the establishment of new relationships among measures of disorder; the introduction of new sorting algorithms that take advantage of the existing order in the input sequence; and, the proofs that several of the new sorting algorithms achieve maximal (optimal) adaptivity with respect to several measures of disorder. The main contributions from the practical point of view are: the demonstration that several algorithms currently in use are adaptive; and, the development of new algorithms, similar to currently used algorithms that perform competitively on random sequences and are significantly faster on nearly sorted sequences. In this survey, we present the basic notions and concepts of adaptive sorting and the state of the art of adaptive sorting algorithms.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	2	Selim G. Akl, Parallel Sorting Algorithms, Academic Press, Inc., Orlando, FL, 1990
	3	T. Altman , Y. Igarashi, Roughly sorting: sequential and parallel approach, Journal of Information Processing, v.12 n.2, p.154-158, Jan. 1989
	4	ARAGON, C., AND SEIDEL, R. 1989. Randomized search trees. In Proceedings of the 30th IEEE Symposzum on Foundatmns of Computer Science. IEEE, New York, 540-545.
	5	BENTLEY, J. L., STANAT, D. F., m~D STEELE, J. M. 1981. Analysis of a randomized data structure for representing ordered sets. In Proceedrags of the 19th Annual Allerton Conference on Communication, Control and Computing, 364-372.
	6	BROWN, M. R., AND TA~AN, R. E 1980. Design and analysis of data structures for representing sorted lists. SIAM J. Cornput. 9, 594-614.
	7	BURGE, W. H. 1958. Sorting, trees and measures of order. Inf. Contr. 1, 181 197.
	8	Svante Carlsson , Jingsen Chen, An optimal parallel adaptive sorting algorithm, Information Processing Letters, v.39 n.4, p.195-200, Aug. 30, 1991 [doi>10.1016/0020-0190(91)90179-L]
	9	Svante Carlsson , Christos Levcopoulos , Ola Petersson, Sublinear merging and natural merge sort, Proceedings of the international symposium on Algorithms, p.251-260, August 1990, Tokyo, Japan
	10	CAYLEY, A. 1849. Note on the theory of permutations. London, Edinburgh and Dubhn Philos. Mug. J. Sc~. 34, 527 529.
	11	CnEN, J., AND CARLSSON, S. 1989. A group-theoretic approach to measures of presortedness. Tech. Rep. Dept. of Computer Science, Lund Univ., Lund, Sweden.
	12	Jingsen Chen , Svante Carlsson, On partitions and presortedness of sequences, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.62-71, January 28-30, 1991, San Francisco, California, United States
	13	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]
	14	DIJKSTRA, E. W. 1982. Smoothsort, an alternative to sorting in situ. Sci. Comput. Program. 1, 223-233.
	15	DINSMORE, R. J. 1965. Longer strings for sorting. Commun. ACM 8, 1 (Jan.), 48.
	16	DoBosmwfcz, W. 1984. Replacement selection in 3-level memories. Comput. J. 27, 4, 334 339.
	17	DROMEY, P. G. 1984. Exploiting partial order with Quicksort. Softw. Pract. Exper 14, 6, 509 518.
	18	Vladimir Estivill-Castro, Sorting and measures of disorder, University of Waterloo, Waterloo, Ont., Canada, 1992
	19	V. Estivill-Castro , D. Wood, A new measure of presortedness, Information and Computation, v.83 n.1, p.111-119, Oct. 1989 [doi>10.1016/0890-5401(89)90050-3]
	20	ESTIVILL-CASTRO, V., AND WOOD, D. 1991a External sorting, initial runs creation, and nearly sortedness. Res. Rep. CS-91-36, Dept. of Computer Science, Univ. of Waterloo, Ontario, Canada.
	21	Vladimir Estivill-Castro , Derick Wood, Practical Adaptive Sorting, Proceedings of the International Conference on Computing and Information: Advances in Computing and Information, p.47-54, May 27-29, 1991
	22	ESTIWLL-CAsTRo, V., ANr~ WOOD, D. t991c Randomized sorting of shuffled monotone sequences. Res Rep. CS-91-24, Dept. of Computer Science, Univ. of Waterloo, Ontario, Canada.
	23	ESTIVILL-CASTBO, V., AND WOOD, D. 1992a. Randomized adaptive sorting. Rand. Struc. Alg. Available as Department of Computer Science Research Report CS-91-21, University of Waterloo To be published.
	24	ESTIVILL-CASTRO~ V., AND WOOD~ D. 1992b. A generic adaptive sorting algorithm. Comput. J. To be published.
	25	ESTWmL-CASTI~O, V., AND WOOD, D. 1992c. An adaptive generic sorting algorithm that uses varmble partitioning. In preparatmn.
	26	ESTIVILL-CASTRO, V., AND WOOD, D. 1992d. The use of exponential search to obtain generic sorting algorithms. In preparation
	27	ESTIVILL-CASTRO, V., MANNILA, H., AND WOOD, D. 1989. Right invariant metrics and measures of presortedness. D~screte Appl. Math. To be published.
	28	W. D. Frazer , A. C. McKellar, Samplesort: A Sampling Approach to Minimal Storage Tree Sorting, Journal of the ACM (JACM), v.17 n.3, p.496-507, July 1970 [doi>10.1145/321592.321600]
	29	W. D. Frazer , C. K. Wong, Sorting by natural selection, Communications of the ACM, v.15 n.10, p.910-913, Oct. 1972 [doi>10.1145/355604.361597]
	30	G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	31	Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, ACM SIGPLAN Notices, v.17 n.6, p.120-126, June 1982
	32	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]
	33	HARRIS, J. D. 1981. Sorting unsorted and partially sorted lists using the natura} merge sort Softw. Pract. Exper. 11. 1339-1340.
	34	Bing-Chao Huang , Michael A. Langston, Practical in-place merging, Communications of the ACM, v.31 n.3, p.348-352, March 1988 [doi>10.1145/42392.42403]
	35	ISLAM, T., AND LAKSHMAN, K. B. 1990. On the error-sensitivity of sort algorithms. In Proceedings of the International Conference on Computing and Informatton. Canadian Scholar's Press, Toronto, 81-85.
	36	Wolfgang Janko, A List Insertion Sort for Keys With Arbitrary Key Distribution, ACM Transactions on Mathematical Software (TOMS), v.2 n.2, p.143-153, June 1976 [doi>10.1145/355681.355685]
	37	Richard M. Karp, Combinatorics, complexity, and randomness, Communications of the ACM, v.29 n.2, p.98-109, Feb. 1986 [doi>10.1145/5657.5658]
	38	KATAJAINEN, J., AND MANNILA, H. 1989. On average case optimality of a presorting algorithm. Unpublished manuscript.
	39	J. Katajainen , C. Levcopoulos , O. Peterson, Local insertion sort revisited, Proceedings of the international symposium on Optimal algorithms, p.239-253, November 1989, Varna, Bulgaria
	40	KENDALL, M. G. 1970. Rank Correlatwn Methods, 4th ed. Griffin, London.
	41	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
	42	LEONG, H. W. 1989. Preorder Heapsort. Tech. Rep. National Univ. of Singapore.
	43	Christos Levcopoulos, On Optimal Parallel Algorithm for Sorting Presorted Files, Proceedings of the Eighth Conference on Foundations of Software Technology and Theoretical Computer Science, p.154-160, December 21-23, 1988
	44	Christos Levcopoulos , Ola Petersson, Heapsort - Adapted for Presorted Files, Proceedings of the Workshop on Algorithms and Data Structures, p.499-509, August 17-19, 1989
	45	C. Lecopoulos , O. Petersson, A note on adaptive parallel sorting, Information Processing Letters, v.33 n.4, p.187-191, December 1989 [doi>10.1016/0020-0190(89)90139-7]
	46	C. Levcopoulos , O. Petersson, Sorting shuffled monotone sequences, Proceedings of the second Scandinavian workshop on Algorithm theory, p.181-191, July 1990, Bergen, Sweden
	47	LEVCOPOULOS, C., AND PETERSSON, O. 1991a. An optimal in-place sorting algorithm. In Proceedings of the 11th Conference on Foundations of Software Technology and Theoretical Computer Science.
	48	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]
	49	LI, M. AND VITANYI, P. M. B. 1989. A theory of learning simple concepts under simple distributions and average case complexity for the universal distribution. In Proceedings of the 30th IEEE Sympostum on Foundatwns of computer Sctence. IEEE, New York, 34 39.
	50	MANNmA, H. 1985a. Instance complexity for sorting and NP-complete problems. Ph.D. dissertation, Univ. of Helsinki, Dept. of Computer Science.
	51	MANNILA, H. 1985b. Measures of presortedness and optimal sorting algorithms. IEEE Trans. Comput. C-34,318 325.
	52	Robert J. McGlinn, A parallel version of Cook and Kim's algorithm for presorted lists, Software—Practice & Experience, v.19 n.10, p.917-930, Oct. 1989 [doi>10.1002/spe.4380191002]
	53	Kurt Mehlhorn, Sorting Presorted Files, Proceedings of the 4th GI-Conference on Theoretical Computer Science, p.199-212, March 26-28, 1979
	54	MEHLHORN, K. 1984. Data Structures and Algorithms. Vol. 1, Sorting and Searching. EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin/Heidelberg.
	55	MOFFA% A. 1990. How good is splay sort. Tech. Rep. Dept. of Computer Science, The Univ. of Melbourne, Parkville, Australia.
	56	MOFF^T, A. 1991. Adaptive merging and a naturally natural merge sort. In Proceedings of the 14th Australian Computer Science Conference, 08.1-08.8.
	57	Alistair Moffat , Ola Petersson, Historical Searching and Sorting, Proceedings of the 2nd International Symposium on Algorithms, p.263-272, December 16-18, 1991
	58	Ola Petersson , Alistair Moffat, A Framework for Adaptive Sorting, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.422-433, July 08-10, 1992
	59	MOFFAT, A., PETERSSON, O., AND WORMALD, N. 1992. Further analysis of an adaptive sorting algorithm. In Proceedmgs of the 15th Austrahan Computer Science Conference, 603 613.
	60	MUNRO, J. I., AND SPIRA, P. M. Sorting and searching in multisets. SIAM J. Comput. 5, i (Mar.), 1976.
	61	T. Papadakis , J. I. Munro , P. V. Poblete, Analysis of the expected search cost in skip lists, Proceedings of the second Scandinavian workshop on Algorithm theory, p.160-172, July 1990, Bergen, Sweden
	62	PETERSSON, O. 1990. Adaptive sorting. Ph.D. dissertation, Lund Univ., Dept. of Computer Science.
	63	PETERSSON, O. 1991. Adaptive selection sorts. Tech. Rep. LU~CS-TR:91-82, Dept. of Computer Science, Lund Univ., Lund, Sweden.
	64	William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
	65	Michael J. Quinn, Designing efficient algorithms for parallel computers, McGraw-Hill, Inc., New York, NY, 1987
	66	Betty Salzberg, File structures: an analytic approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	67	B. Salzberg, Merging sorted runs using large main memory, Acta Informatica, v.27 n.3, p.195-215, Dec. 1989 [doi>10.1007/BF00572988]
	68	SEDGEWICK, a. 1980. Quzcksort. Garland Publishing, New York.
	69	S. S. Skiena, Encroaching lists as a measure of presortedness, BIT, v.28 n.4, p.775-784, 1988 [doi>10.1007/BF01954897]
	70	SLOANE, N. J. A. 1983. Encrypting by ~random rotations. In Proceedings of Cryptography, Burg Feuerstein 82. Lecture Notes in Computer Science 149, Springer-Verlag, New York, 71-128.
	71	TING, T. C., AND WANG, Y. W. 1977. Mult~way replacement selection sort with a dynamic reservoir. Comput. J. 20, 4, 298-301.
	72	VAN GELDER, A. 1991. Simple adaptive merge sort. Tech. Rep. Univ. of California, Santa Cruz, Calif.
	73	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]
	74	WEGNER, L. M. 1985. Quicksort for equal keys, IEEE Trans. Comput. C-34, 362-367.
	75	YAO, A. C. 1977. Probabfiistic computationstoward a unified measure of complexity. In Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, 222-227.
	76	ZHENG, L.-Q, AND LARSON, P.-A. 1992. Speeding up external mergesort. Res. Rep. CS-92-40, Dept of Computer Science, Univ of Waterloo, Ontario, Canada.