Re: A qsort template

On Sun, Apr 10, 2022 at 2:44 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> David Rowley privately reported a performance regression when sorting
> single ints with a lot of duplicates, in a case that previously hit
> qsort_ssup() but now hits qsort_tuple_int32() and then has to call the
> tiebreaker comparator.

That's not good.

The B&M quicksort implementation that we adopted is generally
extremely fast for that case, since it uses 3 way partitioning (based
on the Dutch National Flag algorithm). This essentially makes sorting
large groups of duplicates take only linear time (not linearithmic
time).

-- 
Peter Geoghegan