Re: Timsort performance, quicksort (was: Re: Memory usage during sorting)

On Tue, Apr 24, 2012 at 4:17 PM, Robert Haas <robertmhaas@gmail.com> wrote:
> Based on that, I'm inclined to propose rejiggering things so that the
> presorted-input check runs only at the top level, and not during any
> recursive steps.

Just a thought. What about running only every nth step. Maybe
something like every 4th step.

But actually I'm confused. This seems to be misguided to me. Quicksort
isn't stable so even if you have a partially sorted data set the
recursive partitions are going to be at best partially sorted after a
pivot. I haven't walked through it but suspect even your
all-but-one-sorted data set is not finding
the data sorted in either partition on the next iteration.

-- 
greg