Achieving a high degree of parallelism with efficient
parallel sorting algorithms is difficult on shared memory
multi-processor computers.
I have investigated a few different approaches to the problem on a Sequent
Symmetry computer with four processors, with the FastThread
light-weight thread library. [
1] For external algorithms the
investigation was purely theoretical, but for internal
algorithms I measured the performance with different input data.
The measurement results show that it is possible
to reach almost perfect parallelism and reasonably good
efficiency for internal sorts of large element sets with
short comparison times, and small elements sets with long
comparison times.