GH-116939: Rewrite binarysort() (#116940)

Rewrote binarysort() for clarity.

Also changed the signature to be more coherent (it was mixing sortslice with raw pointers).

No change in method or functionality. However, I left some experiments in, disabled for now
via `#if` tricks. Since this code was first written, some kinds of comparisons have gotten
enormously faster (like for lists of floats), which changes the tradeoffs.

For example, plain insertion sort's simpler innermost loop and highly predictable branches
leave it very competitive (even beating, by a bit) binary insertion when comparisons are
very cheap, despite that it can do many more compares. And it wins big on runs that
are already sorted (moving the next one in takes only 1 compare then).

So I left code for a plain insertion sort, to make future experimenting easier.

Also made the maximum value of minrun a `#define` (``MAX_MINRUN`) to make
experimenting with that easier too.

And another bit of `#if``-disabled code rewrites binary insertion's innermost loop to
remove its unpredictable branch. Surprisingly, this doesn't really seem to help
overall. I'm unclear on why not. It certainly adds more instructions, but they're very
simple, and it's hard to be believe they cost as much as a branch miss.

0 files changed, 0 insertions, 0 deletions