Robert Haas <robertmhaas@gmail.com> writes:
> Yeah, I think I'm going to try implementing
> quicksort-the-whole-batch-and-dump-it-out-as-a-run algorithm, just to
> see how good or bad that is compared to what we have now. We may not
> end up doing anything that remotely resembles that, in the end, but I
> want to see the numbers.
The reason replacement selection is attractive is that the initial runs
tend to be about twice as long as you can get if you just sort
memory-loads independently. (And that's for random input, the win can
be a lot more on partially ordered data.) It seems unlikely that you
will get enough win from quicksorting to overcome that; especially not
if your thesis is correct that all the cost is coming from comparison
infrastructure.
But don't let me discourage you from measuring it ...
regards, tom lane