Sorting

[The Beez]

Hi 4tH-ers!

I've been sorting out things, so to say. First I added two new sorting routines. First, the amazing binary insertion sort, which has an AMAZING performance. Since we got several hybrid ones, I've been testing it. It show that after 64 elements the binary variant really gets onto steam - before the vanilla variant performs better. So, you won't find it in EVERY hybrid routine.

Second, we've added a Timsort variant. There is some discussion on the net whether this is truly Timsort, since it is lacking galloping mode and scanning for sorted sequences, but it sorts and is pretty fast, so we included it. Like Timsort, it uses Insertionsort to sort subsequences (and if they are sorted, they're done in O(n) time) and Mergesort merges these sorted sequences. To make all this clear we've called it "Simple Timsort". The Mergesort we used is "in place", so unlike a true Timsort it doesn't require additional (O(n)) memory.

We also changed the speed table - at least for the "fast" variants. The old way of testing generated many duplicates, so we took one of the many 4tH randomizers (a good one, of course) and remeasured all the speeds at 100,000 elements.

I think we got an impressive list of sorting routines, which I'm very proud of. In case you didn't know, even one I designed and published about ;-) See the Wiki for details.

Hans Bezemer