Introduction

Traditional parallel sorting algorithms, such as the perfect-shuffle bitonic sort, are not suitable for implementation on a shared memory multiprocessor. The main reasons are structural differences and the lack of coordination efficiency. Sequential sorting algorithms, such as Mergesort and Quicksort, do not provide good parallelism when converted in the most obvious manner. For external sorting the problem is not one of processor utilization, but instead one of overall system configuration.

The goal was therefore to develop an internal algorithm as efficient as Quicksort and with good parallelism, and also to find an external algorithm with reasonable parallelism.

Table 1: Used terms.