Accession Number : AD0740110

Title :   Shellsort and Sorting Networks.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Pratt,Vaughan R.

Report Date : FEB 1972

Pagination or Media Count : 64

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. (Author)

Descriptors :   (*COMPUTER PROGRAMMING, LOGIC CIRCUITS), DIGITAL COMPUTERS, GEOMETRY, COMPARATORS, MEMORY DEVICES, SEQUENCES(MATHEMATICS), ALGORITHMS

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE