Table xi compares the performance of our sorting by
regular sampling algorithm with that of our random sample sort algorithm
[14] on both the T3D and the SP-2-WN using the [WR]
benchmark. If 
represents the time required by our regular sample sort algorithm and
represents the time required by our random
sample sort algorithm, then the corresponding entry in Table xi
is 
as a percentage of
. Thus, a negative entry indicates that the regular
sample sort runs faster than the random sample sort algorithm.
The results largely confirm what we would expect:
large values of p together with relatively small values of n make the
performance of our regular sampling algorithm uncompetitive when compared with our sample
sort algorithm. The reason for this is that, unlike our regular sampling algorithm, none
of the steps in our sample sort algorithm exhibit such strong dependence
on p.
But aside from this subset of problems, the performance
of the two algorithms is comparable. Here, regular sampling
would seem to have the advantage, because it deterministically guarantees
the performance bounds and the memory
requirements for any input.
Table xi: Comparison of time required by our regular sampling algorithm with
the time required by our sample sort algorithm using our [WR] benchmark.
If
represents the time required by our regular sampling algorithm and
represents the time required by our random
sample sort algorithm, then the corresponding entry
is as a percentage of
.
Thus, a negative entry indicates that the regular
sample sort runs faster than the random sample sort algorithm.