W. A. Martin
Skip Abstract Section
Abstract
The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years. The basic ideas presented here have been abstracted from this body of work, and the best algorithms known are given as examples. As the algorithms are explained, references to related algorithms and mathematical or experimental analyses are given. Suggestions are then made for choosing the algorithm best suited to a given situation.
- 1 APPLEBAUM, F. H. "Variable word sorting in the RCA 501 System." In Proc. ACM 14th Natl. Conf., 1959, paper #44. Google Scholar
- 2 BARSAMIAN, H. "Firmware sort processor with LSI components." In Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N.J., 183-190.Google Scholar
- 3 BATCHER, K. E. "Sorting networks and their applications." In Proe. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, N.J., 307- 314.Google Scholar
- 4 BAYES, A. "A generalized partial pass block sort." Comm. ACM 11, 7 (July 1968), 491 493. Google Scholar
- 5 BELL, D. A. "The principles of sorting." Computer J. 1, 1 (1958), 71-77.Google Scholar
- 6 BENDER, B. K.; AND A. J. GOLDMAN. "Analytic comparison of suggested configurations for automatic mail sorting equipment." J. Research NBS 63B, 4 (Oct.-Dec. 1959), 83-104.Google Scholar
- 7 BETZ, B. K.; aXD W. C. CARTER. "New merge sorting techniques." In Proc. ACM 14th Natl. Conf., 1959, paper # 14. Google Scholar
- 8 BEUS, H. L. "The use of information in sorting." J. ACM 17, 3 (July 1970), 482-495. Google Scholar
- 9 BLACK, N.A. "Optinmm merging from mass storage." Comm. ACM 13, 12 (Dec. 1970), 745-749. Google Scholar
- 10 BOSE, R. C.; AND R. J. NELSON. "A sorting problem." J. ACM 9, 2 (April 1962), 282-296. Google Scholar
- 11 BRAWN, B. S.; F. G. GUSTAVSON; AND E. S. MANKIN. "Sorting in a paging environment." Comm. ACM 13, 8 (Aug. 1970), 483- 494. Google Scholar
- 12 BURGE, W.H. "Sorting, trees, and measures of order." Information & Control 1 (1958), 181-197.Google Scholar
- 13 CARTER, W. C. "Mathematical analysis of merge-sorting techniques." In Proc. IFIP Cong. 1962, North-Holland Publ. Co., Amsterdam, 1963, 62-66.Google Scholar
- 14 COOKE, W. S. "A tape file merge pattern generator." Comm. ACM 6, 5 (May 1963), 227-230. Google Scholar
- 15 DAVIES, D. W. "Sorting of data on an electronic computer." Proc. Inst. Electronic Engineers (London) 103, Part B supplement (1956), 87-93.Google Scholar
- 16 DE BEAVCbAIR, W. "Das sortieren yon Magnetband-Daten in einfachen Buchungsanlagen." Eleklr. Reehen. 2 (April 1961), 75-82. (German)Google Scholar
- 17 DEFIORE, C.E. "Fast sorting." Datamation 16, 8 (Aug. 1, 1970), 47-51.Google Scholar
- 18 FALKIN, J.; AND S. SAVASTANO, JR. "Sorting with large volume, random access, drum storage." Comm. ACM 6, 5 (May 1963) 240- 244. Google Scholar
- 19 FEERST, S.; AND F. SHERWOOD. "The effect of simultaneity on sorting operations." In Proc. ACM 14th Natl. Conf., 1959, paper #42. Google Scholar
- 20 FLORES, I. "Computer time for address calculation sorting." J. ACM 7, 4 (Oct. 1960), 389-409. Google Scholar
- 21 FLORES, I. "Analysis of internal computer sorting." J. ACM 8, 1 (Jan. 1961), 41-80. Google Scholar
- 22 FLORES, I. Computer sorting. Prentice Hall, Inc., Englewood Cliffs, N.J., 1969. Google Scholar
- 23 FLOYD, R. W.; AND D. E. KNUTH. "Improved constructions for the Bose-Nelson sorting problem." Notices Amer. Math. Society 14 (1967), 283.Google Scholar
- 24 FLOYD, R. W.; AND D. E. KNUTH. "The Bose-Nelson sorting problem." Stanford Computer Science Memo., STAN-CS-70-177, Nov. 1970.Google Scholar
- 25 FORD, L. R.; AND S. M. JOHNSON. "A tournament problem." Amer. Math. Monthly 55 (May 1959), 387-389.Google Scholar
- 26 FOSTER, C. C. "Information storage and retrieval using AVL trees." In Proc. ACM 20th Natl. Conf., 1965, 192-205. Google Scholar
- 27 FOSTER, C.C. "Sorting almost ordered arrays." Computer J. 11, 2 (Aug. 1968), 134-137.Google Scholar
- 28 FRANK, R. M.; AND R. B. LAZARUS. "A high speed sorting procedure." Comm. ACM 3, 1 (Jan. 1960), 20 22. Google Scholar
- 29 FRAZER, W. D.; AND A. C. MCKELLAR. "SAMPLESORT: a sampling approach to minimal storage tree sorting." J. ACM 17, 3 (July 1970), 496-507. Google Scholar
- 30 FREDKIN, E. "Trie memory." Comm. ACM 3, 9 (Sept. 1960), 490--499. Google Scholar
- 31 FRENCH, N. C. "Computer planned collates." Comm. ACM 6, 5 (May 1963), 225-227. Google Scholar
- 32 FRIEND, E .H . "Sorting on electronic computer systems." J. ACM 3, 3 (July 1956), 134-168. Google Scholar
- 33 GALE, D.; AND R. KARP. "A phenomenon in the theory of sorting." In IEEE Conf. Record of the 11th Annual Symposium on Switching and Automata Theory, 1970, 51-59.Google Scholar
- 34 GALLAGER, R.C. Information theory and reliable communication. John Wiley & Sons, New York, 1968. Google Scholar
- 35 GASSNER, BETTY JANE. "Sorting by replacement selecting." Comm. ACM 10, 2 (Feb. 1967), 89-93. Google Scholar
- 36 GILSTAD, R.L. "Polyphase merge sortingan advanced technique." In Proc. EJCC, Vol. 18, Dec. 1960, Spartan Books, New York, 143-148.Google Scholar
- 37 GILSTAD, R.L. "Read-backward polyphase sorting." Comm. ACM 6, 5 (May 1963), 220- 223. Google Scholar
- 38 GLICKSMAN, S. "Concerning the merging of equal length tape files." J. ACM 12, 2 (April 1965), 254-258. Google Scholar
- 39 GLORE, J.B. "Sorting non-redundant filestechniques used in the FACT compiler." Comm. ACM 6, 5 (May 1963), 231-240. Google Scholar
- 40 GOETZ, M. A. "Internal and tape sorting using the replacement selection technique." Comm. ACM 6, 5 (May 1963), 201-206. Google Scholar
- 41 GOETZ, M.A. "Organization and structure of data on disk file memory systems for efficient sorting and other data processing programs." Comm. ACM 6, 5 (May 1963), 245- 248. Google Scholar
- 42 GOETZ, M.A.; AND G. S. ToTH. "Acomparison between the polyphase and oscillating sort techniques." Comm. ACM 6, 5 (May 1963), 223-225. Google Scholar
- 43 GOETZ, M. A. "Design and characteristics of a variable-length record sort using new fixed length record sorting techniques." Comm. ACM 6, 5 (May 1963), 264-267. Google Scholar
- 44 GOETZ, M. A. "Some improvements in the technology of string merging and internal sorting." In Proc. AFIPS 1964 SJCC, Vol. 25, Spartan Books, New York, 599-607.Google Scholar
- 45 GOETZ, M.A. "A disk file sorting problem." In Proc. 3rd Annual Princeton Conf. on In}o. Science and Systems, Dept. Electrical Engineering, Princeton Univ., 1969, 281-285.Google Scholar
- 46 GOTLIEB, C. C. "Sorting on computers." Comm. ACM 6, 5 (May 1963), 194-201. Google Scholar
- 47 HALL, M. H. "A method of comparing the time requirements of sorting methods." Comm. ACM 6, 5 (May 1963), 206-213. Google Scholar
- 48 HIBBARD, THOMAS N. "Some combinatorial properties of certain trees with application to searching and sorting." J. ACM 9, 1 (Jan. 1962), 13-28. Google Scholar
- 49 HIBBARD, THOMAS N. "An empirical study of minimal storage sorting." Comm. ACM 6, 5 (May 1963), 206-213. Google Scholar
- 50 HIBBARD, THOMAS N. "A simple sorting algorithm." J. ACM'IO, 2 (April 1963,) 142- 150. Google Scholar
- 51 HILDEBRANDT, P.; AND H. ISBITZ. "Radix exchange--an internal sorting method for digital computers." J. ACM 5, 2 (April 1959), 156 163. Google Scholar
- 52 HOARE, C. A.R. "Quicksort." Computer J. 5, 1 (1962), 10-15.Google Scholar
- 53 HOSKEN, J. C. "Evaluation of sorting methods." In Proe. EJCC, Vol. 8, Spartan Books, New York, Nov. 1955, 39-55.Google Scholar
- 54 HUBBARD, G. U. "Some characteristics of sorting in computing systems using random access storage devices." Comm. ACM 6, 5 (May 1963), 248-255. Google Scholar
- 55 HWANG, F. K.; AND S. LIN. "An analysis of Ford and Johnson's sorting algorithm." In Proc. 3rd Annual Princeton Conf. on Info. Science and Systems, Dept. Electrical Engineering, Princeton Univ., 1969, 292-296.Google Scholar
- 56 ISAAC, E. J.; AND R. C. SINGLETON. "Sorting by address calculation." J. ACM 3, 3 (July 1956), 169-174. Google Scholar
- 57 JONES, .R.W. "Sorting by merging." Computer J. 2, 2 (July 1959), 95-96.Google Scholar
- 58 KISLITSYN, S. S. "On finding the kth element of an ordered population by means of pair-wise matching." Sibirsky Matem. Zh. 5, 3 (1964), 557-564.Google Scholar
- 59 KNUTH, D. E.; AND M. A. GOETZ. Letter to the Editor. Comm. ACM 6, 10 (Oct. 1963), 585-597. Google Scholar
- 60 KNUTH, D. E. "Length of strings for a merge sort." Comm. ACM 6, 11 (Nov. 1963), 685-687. Google Scholar
- 61 KNUTH, E. D. "Optimum binary search trees." Stanford Computer Science Memo. CS 149, 1970.Google Scholar
- 62 KNUTH, D.E. The art of computer programming, Vol. 3. Addison Wesley Publ. Co., Reading, Mass. (To be published). Google Scholar
- 63 KRONMAL, R.; AND M. TARTER. "Cumulative polygon address calculation sorting." In Proc. ACM 20th Natl. Conf., 1965, 376-385. Google Scholar
- 64 LAUTZ, W. "Sortierverfahren ftir technische Dual-Computer: Part 1." Elektronische Datenverarbeitung, 2 (April 1963), 69-81. (German)Google Scholar
- 65 LAUTZ, W. Sortierverfahren fiir technische Dual-Computer: Part 2." Elektronische. Dalenverarbeitung, 3 (May 1963), 133-141 (German)Google Scholar
- 66 LEHMER, D.H. "Sorting cards with respect to a modulus." J. ACM 4, 1 (Jan. 1957), 41-46. Google Scholar
- 67 LEVY, S. Y.; AiD M. C. PAULL. "An algebra with application to sorting algorithms." In Proc. 3rd Annual Princeton Conf. on Info. Sciences and Systems, Dept. Electrical Engineering, Princeton Univ., 1969, 286-291.Google Scholar
- 68 LIU, D. "Construction of sorting plans." Presented at Internatl. Symposium on the Theory of Machines and Computations, Haifa, Israel, Aug. 1971.Google Scholar
- 69 LYNCH, W.C. "More combinatorial properties of certain trees." Computer J. 7, 4 (Jan. 1965), 299-302.Google Scholar
- 70 MACLAREN, M. D. "Internal sorting by radix plus shifting." J. ACM 13, 3 (July 1966), 404--411. Google Scholar
- 71 MALCOLM, W. D., JR. "String distribution for the polyphase sort." Comm. ACM 6, 5 (May 1963), 217-220. Google Scholar
- 72 MASKER, H. H. "Multiphase sorting." Comm. ACM 6, 5 (May 19637, 214-217. Google Scholar
- 73 MARTIN, W. A.; AND D. N. NESS. "Optimizing binary trees grown with a sorting algorithm." Comm. ACM (to appear). Google Scholar
- 74 MENDOSA, A.G. A dispersion pass algorithm for the polyphase merge." Comm. ACM 5, 10 (Oct. 1962), 502-504. Google Scholar
- 75 MOELLER, D. "MR-1401 a generalized sort program for the card-RAMAC 1401." In IBM Systems Engineering Conf., New York, 1961.Google Scholar
- 76 MORRIS, R. "Scatter storage techniques." Comm. ACM 11, 1 (Jan. 1968), 38-44. Google Scholar
- 77 MORRIS, R. "Some theorems on sorting." SIAM J. Appl. Math. 17, 1 (Jan. 1969), 1-6.Google Scholar
- 78 NAGLER, H. "Amphisbaenic sorting." J . ACM 6, 4 (Oct. 1959), 459-468. Google Scholar
- 79 NAGLER, H. "An estimation of the relative efficiency of two internal sorting methods." Comm. ACM 3, 11 (Nov. 1960), 618-620. Google Scholar
- 80 NICHOLS, J. H.; AND A. TIEDRICH. "A multivariant generalized sort program employing auxiliary drum storage." In Proc. ACM 17th Natl. Conf., 1962. Google Scholar
- 81 O'CONNOR, D.G.;ANDR. J. NELSON. "Sorting system with n-line sorting switch." US Patent 3029413, issued April 10, 1962.Google Scholar
- 82 PAPERNOV, A. A.; AND G. V. STASEVICH. "A method of information sorting in computer memories." Problems of Information Transmission 1, 3 (19677, 63-75.Google Scholar
- 83 PATERSON, J. B. "The COBOL sort verb." Comm. ACM 6, 5 (May 19637, 255-258. Google Scholar
- 84 PICARD, C. "Several recent ideas on the sorting problem." Rev. Franc. Trait. Inf. 9, 1 (1966), 41-46. (French)Google Scholar
- 85 RADKE, C. E. "Merge-sort analysis by matrix techniques." IBM Systems J. 5, 4 (19667, 226-247.Google Scholar
- 86 REYNOLDS, S.W. "A generalized polyphase merge algorithm." Comm. ACM 4, 8 (Aug. 1961), 347-349. Google Scholar
- 87 REYNOLDS, S. W. "Addendum to 'A Generalized Polyphase Merge Algorithm.' " Comm ACM 4, 11 (Nov. 1961), 495. Google Scholar
- 88 SCHICK, T. "Disk file sorting." Comm. ACM 6, 6 (June 1963), 330-331,339. Google Scholar
- 89 SEEBLR, R. R. "Associative self-sorting memory." In Proc. EJCC, Vol. 18, 1960, Spartan Books, N.Y. 179-187.Google Scholar
- 90 SHELL, D. L. "A high speed sorting procedure." Comm. ACM 2, 7 (July 19597, 30-32. Google Scholar
- 91 SHELL, D. L. "Optimizing the polyphase sort." Comm. ACM 14, 11 (Nov. 1971), 713- 719. Google Scholar
- 92 SOBEL, S. "Oscillating sort--a new sort merging technique." J. ACM 9, 3 (July 19627, 372-374. Google Scholar
- 93 SUSSENGUTH, E. H., JR. "Use of tree structures for processing files." Comm. ACM 6, 5 (May 1963), 272-279. Google Scholar
- 94 TARTER, M.E.;ANDR. A. KRONMAL. "Nonuniform key distribution and address calculation sorting." In Proc. ACM 21st Natl. Conf., 1966, MDI Publns., Wayne, Pa., 331- 337. Google Scholar
- 95 VAN EMDEN, M. H. "Increasing the efficiency of quicksort." Comm. ACM 13, 9 (Sept. 1970), 563-567. Google Scholar
- 96 WAKS, DAVID J. "Conversion, reconversion and comparison techniques in variable-length sorting." Comm. ACM 6, 5 (May 19637, 267- 271. Google Scholar
- 97 WIERZHOWSKI, J. "Sorting by means of random access store." Algorytmy 2, 4 (1965), 59-68.Google Scholar
- 98 WINDLY, P. F. "The influence of storage access time on merging processes in a computer." Computer J. 2, 2 (July 1959), 49-53.Google Scholar
- 99 WINDLY, P. F. "Trees, forests, and rearranging." Computer J. 3, 2 (July 1960), 84-88.Google Scholar
- 100 WOODRUM, L. J. "Internal sorting with minimal comparing." IBM Systems J. 8, 3 (19697, 189-203.Google Scholar
- A1 ABRAMS, P. S. "Certification of algorithm 245: Treesort 3," Comm. ACM 8, 7 (July 1965), 445. Google Scholar
- A2 BATTY, M. A. "Certification of algorithm 201: Shellsort." Comm. A CM 7, 6 (June 19647, 349.Google Scholar
- A3 BLAIR, C. R. "Certification of algorithm 207: Stringsort." Comm. ACM 7, 10 (Oct. 1964), 585. Google Scholar
- A4 BLAIR, C. R. "Certification of Algorithm 271: Quickersort." Comm. ACM 9, 5 (May 1966), 354. Google Scholar
- A5 BOOTHROYD, J. "Algorithm 201: Shellsort." Comm. ACM 8, 6 (Aug. 1963,), 445.Google Scholar
- A6 BOOTHROYD, J. "Algorithm 207: Stringsort." Comm. ACM 6, 10 (Oct. 1963), 615. Google Scholar
- A7 BOOTHROYD, J. "Algorithm 25. Sort a section of the elements of an array by determining the rank of each element." Computer J . 10, 3 (Nov. 1967), 308-309.Google Scholar
- A8 BOOTHROYD, J. "Algorithm 26. Order the subscripts of an array section according to the magnitudes of the elements." Computer J . 10, 3 (Nov. 1967), 309-310.Google Scholar
- A9 BOOTHROYD, J. "Algorithm 27. Rearrange the elements of an array section according to a permutation of the subscripts." Computer J. 10, 3 (Nov. 1967), 310.Google Scholar
- A10 CHANDLER, J. P.; AND W. C. HARRISON. "Remark on algorithm 201: Shellsort." Comm. ACM 13, 6 (June 1970), 373-374. Google Scholar
- A11 FEURZEIG, W. "Algorithm 23: Mathsort." Comm. ACM 3, 11 (Nov. 1960), 601. Google Scholar
- A12 FLORES, I. "Algorithm 76: sorting procedures." Comm. ACM 5, 1 (Jan. 1962), 48-50. Google Scholar
- A13 FLOYD, R.W. "Algorithm 113: Treesort." Comm. ACM 5, 8 (Aug. 1962), 434. Google Scholar
- A14 FLOYD, R.W. "Algorithm 245: Treesort 3." Comm. ACM 7, 12 (Dec. 1964), 701. Google Scholar
- A15 GRIFFIN, R.; AND K. A. REDISH. "Remark on algorithm 347: an efficient algorithm for sorting with minimal storage." Comm. ACM 13, 1 (Jan. 1970), 54. Google Scholar
- A16 HILLMORE, J. S. "Certification of algorithlns 63, 64, 65: Partition, Quicksort, Find." Comm. ACM 5, 8 (Aug. 1962), 439. Google Scholar
- A17 HOARE, C. A.R. "Algorithms 63: Partition, and 64: Quicksort." Comm. ACM 4, 7 (July 1961), 321. Google Scholar
- A18 JUELICH, O.C. "Remark on algorithm 175: Shuttlesort." Comm. ACM 6, 12 (Dec. 1963), 739. Google Scholar
- A19 JUELICH, O.C. "Remark on algorithm 175: Shuttlesort." Comm. ACM 7, 5 (May 1964), 296. Google Scholar
- A20 KAUPE, A .F . "Algorithm 143: Treesort 1." Comm. ACM 5, 12 (Dec. 1962), 604. Google Scholar
- A21 KAUPE, A .F . "Algorithm 144: Treesort 2." Comm. ACM 5, 12 (Dec. 1962), 604. Google Scholar
- A22 LONDON, R .L . "Certification of algorithm 245: Treesort 3: proof of algorithms--a new kind of certification." Comm. ACM 13, 6 (June 1970), 371-373. Google Scholar
- A23 PETO, R. "Remark on algorithm 347: an efficient algorithm for sorting with minimal storage." Comm. ACM 13, 10 (Oct. 1970), 624. Google Scholar
- A24 RANDELL, B. "Remark on algorithm 76: sorting procedures." Comm. ACM 5, 6 (June 1962), 348. Google Scholar
- A25 RANDELL, B.; AND L. J. RUSSELL. "Certification of algorithms 63, 64, and 65: Partition, Quicksort, and Find." Comm. ACM 6, 8 (Aug. 1963), 446. Google Scholar
- A26 RANSHAW, R. W. "Certification of algorithm 23: Mathsort." Comm. ACM 4, 5 (May 1961), 238. Google Scholar
- A27 SCHUBERT, G. R. "Certification of algorithm 175: Shuttlesort." Comm. ACM 6, 10 (Oct. 1963), 619. Google Scholar
- A28 SCOWAN, R. S. "Algorithnl 271: Quickersort." Comm. ACM 8, 11 (Nov. 1965), 669- 670. Google Scholar
- A29 SCOWEN, R. S. "Notes on algorithms 25, 26." Computer J. 12, 4 (Nov. 1969), 408-409.Google Scholar
- A30 SHAW, C. J.; AND T. N. TRIMBLE. "Algorithm 175: Shuttlesort." Comm. ACM 6, 6 (June 1963), 312-313. Google Scholar
- A31 SINGLETON, R .C . "Algorithm 347: an efficient algorithm for sorting with minimal storage." Comm. ACM 12, 3 (March 1969), 185-187. Google Scholar
- A32 VAN EMDEN, M. H. "Algorithm 402: increasing the efficiency of Quicksort." Comm. ACM 13, 11 (Nov. 1970), 693. Google Scholar
- A33 WILLIAMS, J. W .J . "Algorithm 232: Heapsort." Comm. ACM 7, 6 (June 1964), 347-348.Google Scholar
- A34 WOODALL, A. D. "Algorithm 43: a listed radix sort." Computer J. 12, 4 (Nov. 1969), 406.Google Scholar
- A35 WOODALL, A.D. "Algorithm 45: an internal sorting procedure using a two-way merge." Computer J. 13, 1 (Feb. 1970), 110-111.Google Scholar
- A36 WOODALL, A. D. "Note on algorithms 25, 26." Computer J. 13, 3 (Aug. 1970), 326.Google Scholar
- A37 WOODALL, A.D. "Algorithm 55: an internal merge sort giving ranks of items." Computer J . 13, 4 (Nov. 1970), 424-425.Google Scholar
Recommendations
Sorting on STAR
This paper gives timing comparisons for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector ...
Block Sorting Is APX-Hard
CIAC 2015: Proceedings of the 9th International Conference on Algorithms and Complexity - Volume 9079Block Sorting is an NP-hard combinatorial optimization problem motivated by applications in Computational Biology and Optical Character Recognition OCR. It has been approximated in P time within a factor of 2 using two different techniques and the ...
Row-Major Sorting on Meshes
In all recent near-optimal sorting algorithms for meshes, the packets are sorted with respect to some snake-like indexing. In this paper we present deterministic algorithms for sorting with respect to the more natural row-major indexing.
For 1-1 ...
Comments