Re: [RFC] new qsort implementation

[Alexander Monakov <amonakov@ispras.ru>]

Hi,

It seems you forgot to commit changes to sorter.h in your repo.

Comparing musl-heapsort to musl-smoothsort, the former appears significantly
better than the latter except on "sorted" input, and even then it's not 20x
faster like the musl commit adding smoothsort claims (about 6.6x for me).  It
does reduce the number of comparisons by 20x there, as the commit says.

There is variation on how divide-and-conquer algorithms in your test handle
sorting on the lowest level; for instance grailsort_ref uses insertion sort
and your implementations use a sorting network (is that correct?).  Would your
comparison be more apples-to-apples if all compared approaches used the same
sorter on the last level, if appropriate (assuming sorting networks improve
performance in some cases)?  

Why did you choose to use sorting networks in your implementations?

For wikisort and grailsort, their "ref" variants perform about 2x faster
on some tests for me .  Is that due to last-level sorter choice, or are there
other significant differences?

Thanks.

Alexander