Access Restriction

Author Kim, Do Jin ♦ Cook, Curtis R.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Merge sort ♦ Insertion sort ♦ Quickersort ♦ Sorting effort measures ♦ Shellsort ♦ Heap-sort ♦ Sorting
Abstract Straight Insertion Sort, Shellsort, Straight Merge Sort,Quickersort, and Heapsort are compared on nearly sorted lists. Theratio of the minimum number of list elements which must be removedso that the remaining portion of the list is in order to the sizeof the list is the authors' measure of sortedness. Tests onrandomly generated lists of various combinations of list length andsmall sortedness ratios indicate that Straight Insertion Sort isbest for small or very nearly sorted lists and that Quickersort isbest otherwise. Cook and Kim also show that a combination of theStraight Insertion Sort and Quickersort with merging yields asorting method that performs as well as or better than eitherStraight Insertion Sort or Quickersort on nearly sorted lists.
Description Affiliation: Oregon State Univ., Corvallis (Cook, Curtis R.) || National Semi-Conductor, Sunnyvale, CA (Kim, Do Jin)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 23
Issue Number 11
Page Count 5
Starting Page 620
Ending Page 624

Open content in new tab

   Open content in new tab
Source: ACM Digital Library