A study of the worst-case of shell-sort
Janet Incerpi · 1986
Shellsort is a well-known sorting method that uses an increment sequence h(,i) and works by performing insertion sort on subfiles consisting of every h(,i)th element. Although the algorithm performs well in practice for moderately sized and almost sorted files, little is known aside from the fact that the running time depends on the increment sequence. In this thesis we study the worst-case complexity of the algorithm. We develop families of increment sequences, with O(log N) increments, that both theoretically and practically are the best known to date. We examine how to generate bad permutations for which Shellsort takes a long time to sort. To this end, we develop the permutation graph. Traversing the graph results in a permutation that is partially sorted. We examine how the permutation graph can be used to generate permutations that have many inversions (one measure of unsortedness) and, in one case, we bound the number of inversions possible. Finally, we look at variations of Shellsort. By allowing linear work per pass, insurance must be given that the file is sorted after O(log N) passes. We describe one such method: it uses LogN passes, has potential as a practical sorting algorithm, and could possibly lead to a simple sorting network.