Shellsort and Sorting Networks
Abstract
Shellsort is a particular method of sorting data on digital computers. Associated with each variant of Shellsort is a sequence of integers that characterizes that variant. In the paper the author answers some open questions about the speed of Shellsort with certain characteristic sequences, and suggests a novel application of Shellsort, namely to sorting networks. Shellsort with any characteristic sequence that approximates a geometric progression and that has short coprime subsequences through takes O(n sup 3/2) units of time. For any sequence that approximates a geometric progression with an integer common ratio, this bound is the best possible. However, if the sequence consists of the descending sequence of positive integers less than n and having only 2 and 3 as prime factors, then Shellsort takes only O(n log squared n) units of time. Sorting networks based on Shellsort with this sequence operate approximately 1.5 times as fast as with previous methods.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1972
- Accession Number
- AD0740110
Entities
People
- Vaughan R. Pratt
Organizations
- Stanford University