Accession Number : AD0740110
Title : Shellsort and Sorting Networks
Descriptive Note : Technical rept.
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Pratt, Vaughan R
PDF Url : AD0740110
Report Date : Feb 1972
Pagination or Media Count : 66
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.
Descriptors : *COMPUTER PROGRAMMING, ALGORITHMS, COMPARATORS, DIGITAL COMPUTERS, GEOMETRY, LOGIC CIRCUITS, MEMORY DEVICES, SEQUENCES(MATHEMATICS)
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE