NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
sorting on starTiming comparisons are given for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's (1962) Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector version of Quicksort that takes advantage of the STAR's vector operations. The third algorithm is an adaptation of Batcher's (1968) sorting algorithm, which makes especially good use of vector operations but has a complexity of N(log N)-squared as compared with a complexity of N log N for the Quicksort algorithms. In spite of its worse complexity, Batcher's sorting algorithm is competitive with the serial version of Quicksort for vectors up to the largest that can be treated by STAR. Vector Quicksort outperforms the other two algorithms and is generally preferred. These results indicate that unusual instruction sets can introduce biases in program execution time that counter results predicted by worst-case asymptotic complexity analysis.
Document ID
19780046024
Document Type
Reprint (Version printed in journal)
Authors
Stone, H. S.
Date Acquired
August 9, 2013
Publication Date
March 1, 1978
Publication Information
Publication: IEEE Transactions on Software Engineering
Volume: SE-4
Subject Category
COMPUTER PROGRAMMING AND SOFTWARE
Funding Number(s)
CONTRACT_GRANT: NSF DCR-74-20025
Distribution Limits
Public
Copyright
Other