Implementing partition on vector computers
Markus Hegland · 1991
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 O( p n) more storage space and comparisons than the original algorithm. 1 Introduction One of the most popular methods for internal sorting is "quicksort" originally proposed by Hoare [7, 9, 4, 18]. It has optimal mean complexity O(n log(n)) which makes it competitive for large data sets even for vector computers running in sequential mode [13]. This motivated the present study on vectorization properties of the kernel of quicksort. Several implementations of quicksort for sequential computers have been investigated to some depth in [7, 8, 16, 14, 15, 10]. Th...