Quick links

Practical Variations of Shellsort

Report ID:
January 1986
Download Formats:


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.

Follow us: Facebook Twitter Linkedin