All in place

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 08/31/2022 at 21:210 Comments

As I'm coding the new version of the algorithm, I realise that I could implement a different approach, and I will probably do it when I can.

The canonical algorithm favours "in place" sorting, which the current version doesn't do (I use a stream of data as a source, not a whole block). The current algo does not need too much adaptation to process an existing block that is already in the "circular playing field" though the efficiency/speed/optimality might be a bit less. It might be a bit simpler though since the runs could be detected progressively and require less room (which is great because the algo uses 2× storage space).

  1. Get your block of data, filling a whole buffer.
  2. Double the size of that buffer and use circular (wrap around) addressing.
  3. Now detect the 4 runs from the tail and from the head. That makes two 4-deep stacks.
  4. Select which runs to merge and where.
  5. loop to 3 until there is only 1 run.

I think I get the idea but it will be better once I can make a video about it :-)

The drawback is that for random data, the tail and head will progressively have longer and longer runs while the middle will still be quite random. The reverse happens in the current version that inserts data one by one, merging runs progressively into larger and larger runs, while the more random data appears on the edges.

Anyway this alternative approach is worth a try !