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
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE