The new file sort_20220831.html.txt is awesome. It implements a lot of the support routines and passes all the tests.

For example it shows the worst case ("Comb") which is exactly the maximum size allocated to the run buffer.

For 256 values to sort, the run "bidirectional stack" needs 128 slots, and the "playground" needs 512 slots. Pretty neat !

I have set the starting point on the "playground" at index 23 but it could be anywhere since all the indices wrap around.

Above, we see the Sine12 test case, showing 4 upslopes (see the green bars at the bottom) and 3 reversed downslopes (blue bar at the bottom right), total: 7 runs.

Steps shows 2 runs, one upwards (green bar at the bottom) starting at index 23, then one downwards, but the light pink "undetermined slope" is popped from the head and moved to the tail before accumulating more downwards samples.

The most crazy cases are still LFSR9, LFSR10 and LFSR14 which have no downslope.

...

Edit

I got a few colors wrong, it's fixed now in the latest code version. Anyway this log was just to prove that the principles I presented previously are totally fine and easy to implement.

Here is the result with the better color scheme and the "origin" in the middle of the range:

• Red is the data accumulated "in reverse" (at the tail)
• Blue is the data accumulated "forward" (at the head)
• Purple is data accumulated at the head but not sure yet if it's going up or down
• Green is the very first item in a run, so it's very undertermined.
• Yellow is undetermined/horizontal block that is moved from the head to the tail.
• Grey is just some original data that was not yet overwritten (just as a visual reminder, since the data is copied before to a temporary buffer)

The goal is to minimise the yellow areas and the new organisation "dual-ended stack" cuts a lot of unnecessary moves compared to the original idea.

The "comb" dataset is the worst case that saturates the run buffer but by definition it can not saturates because the smallest runs can be 2-long. One exception is at the very end, with a run of 1 but the buffer's size is a power of two, and to get the 1-long run, at least one other run must be 3 or a larger odd number. QED.

There is one green bar because since it's the only data yet, there is no need to move it :-)

The initial conditions of the comb matter because here is what it does when the data stream start with the lower value:

Since the first run is "up", the remaining are "up" too and the stack extends to the head. The number of runs does not change though and the runs buffer is totally full yet not overflowing.