Close

Better sorting

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/25/2022 at 02:230 Comments

The new version is here : YAMS_20220925_2.tgz

I added a new counter to help measure the efficiency of the algorithm : I accumulate the sizes of the merged runs. The worst case scenario should be the COMB test pattern that has 128 runs of 2, making 256× log2(128) = 256×7=1792 reads and writes total.

Apparently the algorithm is more efficient (with a lower accumulated score) when all the data are processed at once, and not progressively: the progressive reduction of the data also reduces the choices and the opportunities to merges the smallest runs first. A better heuristic is needed but for now, the progressive merging is disabled, I have run the numbers and they are less favourable than straight bulk merging.

The last log Choosing the next move has been tested and debugged, and it works pretty well. The whole thing is starting to take shape now and it looks good.

Discussions