Close

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/17/2022 at 11:300 Comments

Speculative write !

I've run the numbers in my head and it must work.

I'm not satisfied with a small part of the run detection algo, which writes the first item(s) over the head and must copy it/them when a decreasing run is detected. It works but it is wasteful because the push then the pop and the push sound wasteful.

The solution is to push at both ends simultaneously, then restore one of the stack pointers when the direction is known, to save a pop with all its pointer-management code.

.

_____________________________________________________

.

.

Voilà ! YAMS_20220918.tgz

The sequence of identital values gets written to the head and the tail simultaneously. Only one copy is used in the end (by default the increasing run). The size of the playground is sized just right so there is no problem with a duplication of a maximal length run.

.

Discussions