A List Insertion Sort for Keys With Arbitrary Key Distribution

Publisher Website
Google Scholar
Abstract
An algorithm is described which is an insertion sort producing a single linked list. The sorting method is insensitive to the key distribution. In comparison with alternative insertion sort algorithms like Shellsort algorithms, simple list insertion, and binary tree insertion, this subroutine is comparable in speed with sorting algorithms of the Shellsort type. The number of comparisons is determined by the term O(n 15). In comparison with known alternative sorting methods like quicksort and two-way merge, timing experiments with integer keys showed that the application of the algorithm is very favorable for 5 < n < 50. This may change for extremely long keys and for an ascending or a descending trend in the keys. In the first case, an algorithm which minimizes the number of comparisons (like two-way list merge) is usually faster for sufficiently large n; in the second case, the given algorithm can be favorable even for very large values of n.

This publication has 2 references indexed in Scilit: