QUquuxplusone·Feb 15, 2025
Hmm. I understand the "rainbow" data structure depicted in the paper's Figure 2 (that particular diagram is super useful!), but I don't understand the algorithm to build a (useful) rainbow from an unsorted array. Obviously one way to build a rainbow is to sort the array and then say that the entire array is now the base array of a rainbow, but that's not algorithmically helpful. (Likewise, one can put an array into max-heap (Eytzinger) order simply by reverse-sorting it; but that's not algorithmically helpful.)
So I went to just transcribe the pseudocode algorithm given in the paper, and found instructions like "if index is at the middle of the base array then...", which is pretty confusing at first glance. I believe it just means that we're also tracking the length `L` of the base array, and `if index == (L+1)/2 then...`, but it could be
Read the rest
written much more clearly. (In fact it could just say "if index equals the number of bands.") Likewise the use of the adjectives "middle-left" and "middle-right" instead of spelling out which actual indices we're talking about.
Likewise, when `index` is zero I don't think "base array[index-1]" is well-defined. Seems easy to patch up; but if it's so easy then why didn't the author do it?
The algorithm depends on the undefined subroutines MERGEPOLICY and MERGE. The implementation of MERGE might be considered obvious (if we are unconcerned with the memory consumption of our "band" representation, which also doesn't seem to be concretely described in the paper). MERGEPOLICY, though, is opaque to me, and seems kind of critical to the entire algorithm.
The algorithm runs the opaque BINARYSEARCH step O(n) times, giving it a runtime of O(n log n) right off the bat. This git commit — https://github.com/lewj85/jessesort/commit/b98f7245077681989... — indicates that the author was initially not even aware that sorting is generally O(n log n); he originally wrote that JesseSort was "O(n log(ln n))" with some nonsense about "harmonic numbers." (Thankfully removed in that git commit, but worryingly present before. You cannot in general make a good algorithm simply by starting with a bullshit algorithm and removing the bullshit.)
JesseSort seems to boil down to two steps: (1) Create a list of sorted sublists, using the paper's poorly-defined splitting algorithm. (2) Merge the bands, using the paper's undefined merging algorithm. Up to the details of those two steps it's exactly an N-way mergesort (the dynamic selection of `N` being part of the details). Without reliable concrete explanation of those details, I'm not sure how to proceed.
It almost feels like the author was really excited to share this "rainbow" intermediate data structure (Figures 1 and 2) — which, again, is legitimately interesting IMHO — but when it came to motivating why one might care about it, he just kinda went "I dunno, sorting?" and wasn't really excited about fleshing out that idea beyond a sketch.
P.S., I'm sure this is my C++ chauvinism showing, but I'm shocked that the Python reference implementation operates only on `int`. Surely if you know you're sorting nothing but plain old ints, faster algorithms exist! Python's default `sorted` function works on any kind of input. That probably explains a lot of the speed difference right there. Also, `jessesort` doesn't even fail loudly if you pass it non-ints; it just quietly type-casts the input.
>>> from jessesort_c import jessesort
>>> jessesort([1.414, 2.718])
[1, 2]