Best sorting algorithm for nearly sorted lists
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.