JesseSort: A novel sorting algorithm that is faster than Python's default sort.

I’d like to see a much larger n but the charts in the research paper aren’t really selling JesseSort. I think as more and more “sorts” come out, they all get more niche. JesseSort might be good for a particular dataset size and ordering/randomness but from what I see, we shouldn’t be replacing the default Python sorting algorithm.

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 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]

As general things, timsort was aimed at exploiting all kinds of pre-existing order, not random lists. The only goal for the latter was to be within reach of CPython's previous highly tuned samplesort implementation (like quicksort on steroids, with much less data movement than mergesorts, but more comparisons).

As you say, for randomly ordered input it gets remarkably close to the information-theoretic lower bound on # of compares. So that's not it.

"Cache effects", maybe, but that's a pit to dig into. I'll note that while the newer "powersort" merge strategy is elegant and provably near-optimal by some relevant measures, in practice it doesn't really appear to run any faster (although cases can be _contrived_ that make it - or the older method! - run faster).

Comparison specialization (to ints) could very well account for it. CPython's general comparison machinery is _very_ expensive, even for what turn out to be native machine ints (which CPython cannot know at compile-time: everything is deduced at runtime).

CPython has since grown new machinery to do a pre-pass over the list, and do a form of cheaper comparison specialization for what turn out to be homogeneous lists of suitable types (including "small enough" ints). That alone gives enough speedup to make some of the original choices sub-optimal. For example, binary insertion sort for short runs is no longer best then. That was aimed at minimizing worst-case # of compares, but as comparisons get cheaper that has less value.

There are also surprises in everything. For example, the worst case for binary insertion sort on most machines was _not_ reverse-ordered input, despite that it requires the most data movement. Instead the worst case was randomly ordered data. Why? Branch prediction. In randomly ordered data, each branch is unpredictable. In reverse-ordered data, "move to the left" is always the test outcome.

Another generality is that Python's sort cares more about speed for shorter lists than huge ones. "Big data" problems are more likely to use, e.g., extensions geared to "big data problems", like numpy for giant arrays of floats. In those contexts more suitable _algorithms_ exist, like radix sorts, or multi-key quicksorts for lists of long strings with long shared prefixes.

Python's niche is more in, e.g., web services, where a great many sorts of shorter lists are common.

Bottom line: there is no one "best" sorting algorithm. I keep an eye out for newer developments, but haven't seen anything better yet for what Python is aiming at. I was, e.g., very impressed by pdqsort - but it's not a stable sort, and that alone makes it a non-starter for general Python use.

One thing that wasn't clear to me about JesseSort: in what way(z) are Rainbows believed to be an improvement over the simpler scheme used by the older "patience sorting"? They both maintain a collection of sorted sublists merged at the end, both use binary search to find the right sublist to add "the next" array element to, and both excel at "low diversity" inputs (if there are K distinct values, patience sorting will build at most K sublists).

As I recall, full-blown patience sorting isn't "naturally stable". Searching through the JesseSort paper, I didn't find it addressed, and the details were too fuzzy to guess offhand. While this is in no way a principled objection, it just _seemed_ "too complicated" to me. Then again, my intuition for such things has served me well before ;-)