Practical Variations of Shellsort

Abstract:

Shellsort is based on a sequence of integer increments h, and works by performing insertion sort on subfiles consisting of every h,th element. We consider variations of Shellsort that limit the work performed per
pass. By allowing only 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 log N passes, has potential as a practical sorting algorithm, and could possibly lead to a simple sorting network.