On Wed, Apr 26, 2017 at 8:20 PM, Peter Geoghegan <pg@bowt.ie> wrote:
On Wed, Apr 26, 2017 at 10:10 AM, Alexander Korotkov <a.korotkov@postgrespro.ru> wrote: > OK, I get it. Our qsort is so fast not only on 100% presorted case. > However, that doesn't change many things in context of incremental sort.
The important point is to make any presorted test case only ~99% presorted, so as to not give too much credit to the "high risk" presort check optimization.
The switch to insertion sort that we left in (not the bad one removed by a3f0b3d -- the insertion sort that actually comes from the B&M paper) does "legitimately" make sorting faster with presorted cases.
I'm still focusing on making incremental sort not slower than qsort with presorted optimization. Independently on whether this is "high risk" optimization or not...