There have been many suggestions of ways to improve the performance of sequential quicksort (see, for example, Wainwright, 1985 and the references therein). The following are two suggestions that have...

There have been many suggestions of ways to improve the performance of sequential quicksort (see, for example, Wainwright, 1985 and the references therein). The following are two suggestions that have appeared in the literature: 1. Rather than selecting the first number as the pivot, use the median of a group of three numbers picked randomly (“median-of-three” technique). 2. The initial set of numbers is divided into two parts using the first number as the pivot. While the numbers are being compared with the pivot, the sum of the numbers in each of two parts is computed. From these sums, the mean of each part is computed. The mean of each part is used as the pivot for this part in the next partitioning stage. The process of computing two means is done in subsequent stages for the next pivots. This algorithm is called the meansort algorithm. Determine empirically the prospects for parallelizing these methods.