On Thu, Nov 19, 2015 at 5:32 PM, Greg Stark <stark@mit.edu> wrote:
> Hm. Have you tested a nearly-sorted input set around 1.5x the size of
> work_mem? That should produce a single run using the heap to generate
> runs but generate two runs if, AIUI, you're just filling work_mem,
> running quicksort, dumping that run entirely and starting fresh.
Yes. Actually, even with a random ordering, on average replacement
selection sort will produce runs twice as long as the patch series.
With nearly ordered input, there is no limit to how log runs can be --
you could definitely have cases where *no* merge step is required. We
just return tuples from one long run. And yet, it isn't worth it in
cases that I tested.
Please don't take my word for it -- try yourself.
--
Peter Geoghegan