After I stopped trying to improve on the performance of crystal sort (https://mossgoblin.com/sommath/2021/06/25/sorting-them-numbers/), I was left with the idea of the unused sorting algorithms.
See, the thing is, once the ball is rolling (the ball of finding the best solution of a problem, that is), it doesn’t stop to make sure it has covered all the path beneath it. In fact it doesn’t roll, it bounces. And wherever it touches the ground you have your next best solution. So a lot of ground never gets touched. You know how high the bar currently is and you know where you should start thinking onwards if you want to raise it even more. So, I think, there’s enough uncharted ground beneath that high performance bar for one to wander about.
Meaning – there are a lot of low hanging fruit to be picked, if you are so inclined. The point? Well, there’s exploration. That’s reason enough in and of itself. For me it is almost the same as finding yet another proof of the Pythagorean theorem. Not that anyone needs it, per se, but boy would I be proud if I found one!
I would not be as proud to find a relatively slow sorting algorithm, but it does please me enough.
Hence – Push Sort.
(to be properly documented and repo’d)
Again (as with crystal sort) I named it myself. Even though undoubtedly it has been by someone considered half a century (or more) ago, it is clearly not clever enough to be performing well, so it has sunk in obscurity.
It is a very brute force approach and I was surprised that it ranked in the middle of the test table – I gotta cite some data, but if I remember correctly it was somewhere around merge, I think. See the comparison algorithms I used in the readme of crystal sort’s repo (I reused the benchmarking base).
The idea is very simple – take the elements from the bucket one by one and move them into a sorted bucket, placing them in the correct place within all other already placed elements. Let’s say you choose to sort ascending. You take the next bucket element and compare with the first sorted element. If the new is smaller or equal, insert it there (place in at index 0 and shift the others). If it is larger, repeat comparison with the next. If there is no next, then you have the largest element so far, so place it at the end.
As I said – it works surprisingly well. No trailblazer, for sure, but still.
Anyways. I have more to say about the low hanging fruit, but I’ll leave that for some other time. May be with the next mediocre sorting algorithm.
P.S. I should start using pseudocode and code blocks here…