Re: [PATCH] stdlib: Optimize number of calls to comparison function

[Florian Weimer <fweimer@redhat.com>]

* Kuan-Wei Chiu:

> The current heapsort implementation in the siftdown function follows
> the standard textbook version, necessitating two comparisons at each
> level. Transitioning to the Bottom-up heapsort version allows us to
> decrease the required comparisons to just one per level. On average,
> this modification significantly reduces the comparison count from
> 2nlog2(n) - 3n + o(n) to nlog2(n) + 0.37*n + o(n).

I think the factor in stdlib/tst-qsort5.c needs to be adjusted:

  /* This is an arbitrary factor which is true for the current
     implementation across a wide range of sizes.  */
  TEST_VERIFY (factor <= 4.5);

On the other hand, the heapsort code is not really expected to run at
all in the current implementation because median-of-three quicksort
usually avoids degenerating behavior.  If this heapsort variant uses a
number of comparisons that is competitive to quicksort, maybe we should
use it instead?  And use insertion sort for short arrays only.

Thanks,
Florian