Algorithms for sorting nearly sorted lists
Type of content
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
Journal Title
Journal ISSN
Volume Title
Language
Date
Authors
Abstract
The following five algorithms for sorting in situ are examined: linear insertion sort, cksort, natural mergesort, ysort and smoothsort. Quicksort and heapsort are also considered although they are not discussed in detail. The algorithms have been implemented and compared, with particular emphasis being placed on the algorithms' efficiency when the lists are nearly sorted. Five measures of sortedness are investigated. These are sortedness ratio, number of inversions, longest ascending sequence, number of ascending sequences, and number of exchanges. The sortedness ratio is chosen as a basis for comparison between these measures and is used in experiments on the above algorithms. Improvements to cksort and ysort are suggested, while modifications to smoothsort and linear insertion sort failed to improve the efficiency of these algorithms.