In:
Communications of the ACM, Association for Computing Machinery (ACM), Vol. 23, No. 11 ( 1980-11), p. 620-624
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.
Type of Medium:
Online Resource
ISSN:
0001-0782
,
1557-7317
DOI:
10.1145/359024.359026
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
1980
detail.hit.zdb_id:
80254-2
detail.hit.zdb_id:
2004542-6
Permalink
