On Monday, 20 May 2019 at 02:18:51 UTC, Era Scarecrow wrote:
Here's some outputs if you are interested
Noticing how Heapify moves a large portion of areas more or less
in their location, doing heapify before binary insertion sort
lowers how much moving goes on quite a bit. Doing 2 heapify's
dropped in my test down a lot.
An interesting idea to throw in partial ideas from other sorts
to make a more efficient one.
So binary insertion sort heap(min): BISH
Some experiments to be done, but looks interesting.
Sorting a 44 character string/array (quick brown fox) took about
250 comparisons and similar moves. I removed a bunch that are
likely an assert in the final check/run of the heapify.
Original binary insertion sort was 154 comparisons and 466 moves.
Bish sort was 259 & 284 moves
https://pastebin.com/raw/rJ1aWmD1