Best sorting algorithm for nearly sorted lists

ABSTRACT

Straight Insertion Sort, Shellsort, Straight Merge Sort, Quickersort, and Heapsort are compared on nearly sorted lists. The ratio of the minimum number of list elements which must be removed so that the remaining portion of the list is in order to the size of the list is the authors' measure of sortedness. Tests on randomly generated lists of various combinations of list length and small sortedness ratios indicate that Straight Insertion Sort is best for small or very nearly sorted lists and that Quickersort is best otherwise. Cook and Kim also show that a combination of the Straight Insertion Sort and Quickersort with merging yields a sorting method that performs as well as or better than either Straight Insertion Sort or Quickersort on nearly sorted lists.

REFERENCES

• 1: Boothroyd, J. Algorithm 201: Shellsort. Comm. ACM 6, 8 (Aug. 1963), 445.
• 2: J. Boothroyd, Algorithm 207: stringsort, Communications of the ACM, v.6 n.10, p.615, Oct. 1963 [doi>10.1145/367651.367662]
• 3: Elson, M. Data Structures. Sci. Res. Associates, Chicago, IlL, 1975. An excellent data structures textbook with a chapter on sorting.
• 4: Robert W. Floyd, Algorithm 245: Treesort, Communications of the ACM, v.7 n.12, p.701, Dec. 1964 [doi>10.1145/355588.365103]
• 5: Fredman, M.L. On computing the length of longest increasing subsequences. Discrete Math. 11 (1975), 29-35. Describes a simple algorithm using order n log n comparisons to fred the length of a longest increasing subsequence in a sequence of n distinct elements. The algorithm is also shown to be the best possible.
• 6: C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
• 7: 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
• 8: Rudolf Loeser, Some performance tests of “quicksort” and descendants, Communications of the ACM, v.17 n.3, p.143-152, March 1974 [doi>10.1145/360860.360870]
• 9: M. Donald MacLaren, Internal Sorting by Radix Plus Sifting, Journal of the ACM (JACM), v.13 n.3, p.404-411, July 1966 [doi>10.1145/321341.321349]
• 10: W. A. Martin, Sorting, ACM Computing Surveys (CSUR), v.3 n.4, p.147-174, Dec. 1971 [doi>10.1145/356593.356594]
• 11: Kurt Mehlhorn, Sorting Presorted Files, Proceedings of the 4th GI-Conference on Theoretical Computer Science, p.199-212, March 26-28, 1979
• 12: R. S. Scowen, Algorithm 271: quickersort, Communications of the ACM, v.8 n.11, p.669-670, Nov. 1965 [doi>10.1145/365660.365678]
• 13: vanEmden, M.H. Algorithm 402: qsort. Comm. ACM 13, I l (Nov. 1970), 693-694.
• 14: Williams, J.W.J. Algorithm 232: Heapsort. Comm. ACM 7, 6 (June 1964), 347-348.

INDEX TERMS

Keywords:
Quickersort, Shellsort, heap-sort, insertion sort, merge sort, sorting, sorting effort measures