YALO! (Yet Another Little Optimisation)

A project log for YAMS Yet Another Merge Sort

There are already so many sorting algorithms... So let's make another!

yann-guidon-ygdesYann Guidon / YGDES 09/22/2022 at 02:470 Comments

Something else to consider :

The blue bloc on the right is made of 3 separate runs. However, since their max/last value est lower than the min/first value of the next run, they could be merged. Which is a potent optimisation for random data, where a non-insignificant fraction of the very short runs could fall in this case. I have to get to work on this too...


And it works ! These are the new "notch" and "hcton" pattern buttons, the run management system correctly merges those that match the criterion. It's not often but it's still good to have/do.

It is used from time to time in the random patterns. It is not too heavy but makes it harder to inline the RunHeadPush() and RunTailPush() functions, where the magic goes.