Implementing partition on vector computers

Hegland, Markus

Cultural advice

The Australian National University acknowledges, celebrates and pays our respects to the Ngunnawal and Ngambri people of the Canberra region and to all First Nations Australians on whose traditional lands we meet and work, and whose cultures are among the oldest continuing cultures in human history.

Aboriginal and Torres Strait Islander peoples are advised that ANU Library collections may include images, names, voices, and other representations of deceased persons.

Material in the collection may contain terms, language or views that reflect the period in which the item was created and may be considered inappropriate today.

Implementing partition on vector computers

Date

1991-06-01

Authors

Hegland, Markus

Abstract

The partitioning of an array is the basic building block of many efficient sorting algorithms. Here we study three ways to implement partitioning on vector supercomputers. A data model is presented with which the performances of these algorithms are analyzed. Performance is also measured on one processor of a Cray X-MP. Speedups between four and seventeen have been obtained for large data sets for an implementation using only 0(√n) more storage space and comparisons than the original algorithm.