Summary

I have shown that with a lot of programming effort it is possible to increase the parallelism of Quicksort. Unfortunately the ``Improved'' Parallel Quicksort as examined here is still less efficient than the usual Parallel Quicksort implementation, which means that it won't perform satisfactory when the time to compare elements is on the same order of magnitude as the overhead of the sorting algorithm.

The Improved Parallel Quicksort has much potential for improvement however. With more programming and tuning effort it should provide better performance than Parallel Quicksort on four processors even for short comparison times.

Regarding external algorithms, the improvement from using more than one processor is much smaller than for the internal algorithms. With the restrictions and conditions given for the respective algorithms, both Simple External sort and Improved Block Bitonic sort are suitable for real-life applications. The Improved Block Bitonic provides somewhat better performance than the Simple External sort, but requires that the I/O system be organized for parallelism.