Best sorting algorithm for nearly sorted lists
- 1 November 1980
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 23 (11), 620-624
- https://doi.org/10.1145/359024.359026
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.Keywords
This publication has 9 references indexed in Scilit:
- On computing the length of longest increasing subsequencesDiscrete Mathematics, 1975
- Some performance tests of “quicksort” and descendantsCommunications of the ACM, 1974
- SortingACM Computing Surveys, 1971
- Algorithms 402: Increasing the efficiency of quicksortCommunications of the ACM, 1970
- Internal Sorting by Radix Plus SiftingJournal of the ACM, 1966
- Algorithm 271: quickersortCommunications of the ACM, 1965
- Algorithm 245: TreesortCommunications of the ACM, 1964
- Algorithm 207: stringsortCommunications of the ACM, 1963
- Algorithm 64: QuicksortCommunications of the ACM, 1961