5 ms·

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

98 points by amichail 2y ago

quuxplusone 2y ago
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 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/b98f7245077681989360a85102273026882067e1 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]
hinkley 2y ago
So for those of us who aren’t hanging on every update in the Python universe, what is the default sort in Python now? All I recall is that Timsort got dethroned and the author seems to be behaving like it’s some big secret to be kept from the plebs. Edit: all the way at the bottom of page 6: timsort+powersort
- vanderZwan 2y ago
  Powersort is pretty neat, here's a blog post with links to talks about it by one of the authors: https://www.wild-inter.net/posts/powersort-in-python-3.11 https://www.wild-inter.net/posts/powersort-in-python-3.11
pinoy420 2y ago
Why is this implemented in python? Is it compiled some how?
- 00ajcr 2y ago
  There's a Cython implementation (the .pyx file). The Cython code is compiled to C code (then that C code is compiled).
vanderZwan 2y ago
Interesting approach, although I'm wondering why they didn't just use a double-ended queue instead of a linked list. Also, I get the urge to name the algorithm after yourself, since Timsort is named after its creator as well, but if you call you data structure "rainbow" then my first association would be the rainbow flag, since flag-sorts also have a tradition in sorting algorithm names. [0] https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem [1] https://en.m.wikipedia.org/wiki/American_flag_sort https://en.m.wikipedia.org/wiki/American_flag_sort
- ipsum2 2y ago
  First thing I think about with "rainbow" and "data structures" is rainbow tables.
- blibble 2y ago
  a double-ended queue is often implemented using a doubly linked list (like the one in use here) if you back it by two arrays then you can't do O(1) inserts in the middle (like is going on here)
  - tialaramex 2y ago
    It's true that awful Deque implementations are often built from a linked list. If you're taught about big-O notation and haven't noticed how modern computers work you might even do that today. I would expect that they're thinking of something more like Rust's VecDeque, so that's a conventional "growable array" (Rust's Vec, Java ArrayList, C++ std::vector) used internally with some head + tail tracking to form a circular buffer so as to deliver the Deque API (fast push to head or tail, fast pop from head or tail).
    - blibble 2y ago
      you can make mechanically sympathetic linked lists with low constant factors as long as you avoid pointers
AutistiCoder 2y ago
so, I had ChatGPT give me a quick run through, after feeding it the JesseSort python file, here's how it understood the algorithm in simple terms: 1. It starts with two elements and places them in order. 2. Each new element is inserted into the correct position within the growing "rainbow" of sorted bands. 3. By the time all elements are inserted, the list consists of multiple sorted bands that are then merged. Was it wrong?
- earnestinger 2y ago
  Pdf mentions split rainbows
drpixie 2y ago
If you're going to make a big claim about sort speed, tell me how speed is better/worse for various data. How do the algorithms compare when the data is already ordered, when it's almost (but not quite) already ordered, when it's largely ordered, when it's completely random, and it's in the opposite order. This stuff, as well as the size of the dataset, is what we need to know in practice.
- sambeau 2y ago
  https://www.researchgate.net/publication/388955884_JesseSort https://www.researchgate.net/publication/388955884_JesseSort
  - deleted 2y ago
    [deleted]
  - nimih 2y ago
    What's your point? The paper you're linking does not include the analysis the post you're responding to is asking for.
    - gymbeaux 2y ago
      It does give some insight into what you seek, at least. For example, “We ﬁnd that for smallern≲262144, JesseSort is slower 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.
- tialaramex 2y ago
  Rather than, or at least in addition to, raw measured speed on a specific piece of hardware, which is often affected in hard to understand ways by niche optimisation choices and nuances of specific hardware, I actually really like the choice to report how many comparisons your algorithm needed. For example Rust's current unstable sort takes ~24 comparisons on average for each of 10^7 truly random elements to sort them all, but if instead all those elements are chosen (still at random) from only 20 possibilities, it only needs a bit more than five comparisons regardless of whether there are 10^3 elements or 10^7. Unlike "On this Intel i6-9402J Multi Wazoo (Bonk Nugget Edition) here are my numbers" which is not very useful unless you also have the i6-9402J in that specific edition, these comparison counts get to a more fundamental property of the algorithm that transcends micro architecture quirks which will not matter next year.
behnamoh 2y ago
I have mixed feelings about the naming. Isn't it kinda off-putting that he named it after himself? usually it's other people who name your algorithm after you. At least that's how it's like in science and engineering (Fourier didn't call it "Fourier transform", Laplace didn't call it "Laplace transform", Kalman didn't name it "Kalman filters", etc.)
- gyudin 2y ago
  Like Dijkstra's algorithm? Knuth-Morris-Pratt algorithm? Huffman coding?
  - charlieyu1 2y ago
    Did any of these guys put their name on the algorithm by themselves?
    - vanderZwan 2y ago
      The author seems young, I think we should be a little forgiving if they saw all these algorithms and concluded "ok so if you come up with something new you get to name it after yourself"
  - quuxplusone 2y ago
    Not to mention Shellsort. https://en.wikipedia.org/wiki/Donald_Shell https://en.wikipedia.org/wiki/Donald_Shell
  - behnamoh 2y ago
    those names were given to those algorithms by others, not the creators.
    - gymbeaux 2y ago
      What did they call their algorithms before they passed away?
xiaodai 2y ago
Python's default is gallop sort however radixsort is much faster and performs in O(n).
- ijustlovemath 2y ago
  I thought it was Timsort?
  - pstoll 2y ago
    It was and always will be timsort-ly yours. iykyk.
- selcuka 2y ago
  > radixsort is much faster and performs in O(n). Radix sort time complexity is not O(n); it's O(n*k) where k is the size of the largest element. Besides it has an additional O(n+k) space complexity.
- perlgeek 2y ago
  radixsort isn't a comparison-based sort algorithm, so you're comparing apples to chickens.
prirun 2y ago
"We ﬁnd that for smaller n≲ 262144, JesseSort is slower than Python’s default sort."
- repsilat 2y ago
  I wonder about the global statistics of sorted data... Is the most common number of elements to sort zero? Certainly less than ten? What about the median? Two elements to sort? One? Zero again?
  - lblume 2y ago
    The question is also for which list lengths the performance matters most. When sorting a few strings (<20), whether the algorithm uses 5 or 7 comparisons would usually not matter too much. So to find the optimal algorithm for a given situation, we would have to compute a weighted average by list length importance on the performances of the algorithm per list length.
- 3eb7988a1663 2y ago
  Don't high performance systems have heuristics to decide what specific algorithms to use at runtime? It is not unimaginable to think that there could be a function dedicated to small vs large collections. Assuming the results hold, someone has to decide if the additional complexity is worth the performance. For something like BLAS, go nuts. For Python standard library, maybe not.
agnishom 2y ago
I am a bit concerned that the primary channel of distribution of the paper is ResearchGate. I am somehow biased against taking it seriously because of this.
mlochbaum 2y ago
So the idea is that you'll eventually arrange n elements into ideally about √n sorted lists, organized so that the endpoints of these lists are also ordered (the "rainbow" shape). A new element goes on the end of one of those lists or a new list; which one is generally decided by binary search, but the index is saved to speed up the next insertion if it's the same. So a natural run might benefit by having adjacenct values inserted to the same list. Which cases benefit and which don't seems potentially quite erratic. If you have a series of runs that shrink over the course of the array, with increasing start value and decreasing start value, each will become a new sorted list and you end up with O(n) insertion plus a perfect merge. If the runs get wider instead, they'll cross over existing endpoints and end up spattered around before merging. It feels like the paper keeps trying to spin constant-factor improvements as somehow being asymptotically relevant despite acknowledging that mathematically they aren't, for example the fact that log(√n) is only log(n)/2 "would not reflect the sublinear nature of base array length k" and runs hitting the best case "approximately 50% of the time... reinforces JesseSort's average runtime complexity as somewhere between O(n) and O(n log_2 n)". Powersort provably takes O(n + n log r) worst-case time where r is the number of runs; I expect this algorithm is O(n log n) worst- and average-case. However, on random arrays the given benchmarks do improve relative to Python default as the length increases, with faster performance starting a little under a million elements. There isn't a lot of investigation into why this is. I'd be interested to know if the number of comparisons is reduced in particular. Perhaps this algorithm is more cache-friendly with a random input, but this wouldn't be reliable as many inputs can cause the number of sorted lists to scale with O(n) so that the binary searches need to work on a large array.
- mlochbaum 2y ago
  The analysis would make a lot more sense if it dropped every big O and computed an expected number of comparisons. Of course, the real issue is that the whole thing relies on an empirically-determined length of √8√n for the number of lists in the rainbow, when the theoretical justification isn't there and clearly the worst case is n/2. I'm not seeing any awareness that the expected number of comparisons has to be at least log_2(n!), and am starting to see some worrying signs that the author thinks averages like n log log n are possible. I'd initially assumed that "somewhere between O(n) and O(n log_2 n)" statement meant in the presence of asymptotically large natural runs, but there's a claim that the runs "need not be of any minimum size" and another that the algorithm can "capitalize on natural runs" that seems to be referring to the benchmarks on "purely random values".
ggm 2y ago
"This journal no longer accepts papers on optimal solutions to the 9 queens problem"
funnyAI 2y ago
[dead]
vivzkestrel 2y ago
I know it is not possible in our Universe but on a lighter note, in some parallel universe out there, someone has made a sorting algorithm that runs in O(1). I wonder though if a quantum computer can simultaneously sort all the elements in O(1)
- warkdarrior 2y ago
  "quantum computers are no better than classical ones [for sorting]" https://en.m.wikipedia.org/wiki/Quantum_sort https://en.m.wikipedia.org/wiki/Quantum_sort
- procaryote 2y ago
  If you can pick parallel universes, just pick the one where the data happens to be sorted
- henry2023 2y ago
  A modern Borges could write a really good short story about that universe.
tcper 2y ago
Amazing, there is still new sort algorithm today!
conradludgate 2y ago
And what about pdqsort, glidesort, driftsort, ipnsort? New research is always cool, but there's plenty of other research in this space to compare this to
tim-peters 2y ago
I want to elaborate on timing cautions: a sort that specializes to 4-byte machine ints is doing something that can't be expressed directly in CPython. Its lists are heterogeneous, types aren't known until runtime, and there is no native (to Python) concept of "4-byte int". All CPython ints are stored in "bigint" (unbounded) format, and even zero requires 32 bytes of storage in the format (overheads for a type pointer, refcount, 16-byte heap alignment padding). That format isn't 2's complement either (although it creates the semantic _illusion_ of being such): it's sign+magnitude. The general object comparison machinery is very expensive at runtime, essentially repeated from scratch on every compare. To mitigate this, CPython does a prepass over the list (O(n)) to see whether the list is in fact homogenous, and, if so, of a type that can use a more specialized comparison function. Not free, but pays off hugely if you are in fact sorting a list of "small enough" machine ints. But it doesn't change the storage format: on every compare, cycles are still consumed to transform CPython's sign+magnitude bigint format to native 2's-complement for native machine code to compare directly. I expect this accounts for most of the observed "speedup" over timsort. Despite semi-heroic efforts to cut the cost, comparisons of native ints in CPython will always be significantly more expensive than code specialized to compare native ints directly. At least until (if ever) CPython learns how to "unbox" ints. The PyPy implementation of Python already does, and sorting lists of native machine ints runs about twice as fast under PyPy. It's not the sorting algorithm that matters to this, it's the relative cost of machine-int compares, and almost certainly too the cache pressure of using many more bytes to store small ints than necessary in "boxed" format. As mentioned elsewhere, JesseSort reminds me most of the old and simpler "patience sorting", with which it has a lot in common. Both keep a collection of sorted sublists (to be merged at the end), both use binary search to pick a collection member to which to add 'the next" input, both excel at "low diversity" inputs, both (on average) end up with O(sqrt(n)) sublists on randomly ordered inputs, and neither is "naturally" stable. As I noted in listsort.txt at the time, while timsort gets a lot of value out of repeated elements ("low diversity"), it's just not the right approach to exploit that aa much as possible. JesseSort and pdqsort (and, by extension, glidesort) will always do better on that. OTOH, timsoet gets value out of many kinds of partial ordering, which "reveal themselves" dynamically via one run in a merge "winning" consistently.

98 points by amichail 2y ago

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

hinkley 2y ago

So for those of us who aren’t hanging on every update in the Python universe, what is the default sort in Python now? All I recall is that Timsort got dethroned and the author seems to be behaving like it’s some big secret to be kept from the plebs. Edit: all the way at the bottom of page 6: timsort+powersort

vanderZwan 2y ago
Powersort is pretty neat, here's a blog post with links to talks about it by one of the authors: https://www.wild-inter.net/posts/powersort-in-python-3.11 https://www.wild-inter.net/posts/powersort-in-python-3.11

pinoy420 2y ago

Why is this implemented in python? Is it compiled some how?

00ajcr 2y ago
There's a Cython implementation (the .pyx file). The Cython code is compiled to C code (then that C code is compiled).

vanderZwan 2y ago

Interesting approach, although I'm wondering why they didn't just use a double-ended queue instead of a linked list. Also, I get the urge to name the algorithm after yourself, since Timsort is named after its creator as well, but if you call you data structure "rainbow" then my first association would be the rainbow flag, since flag-sorts also have a tradition in sorting algorithm names. [0] https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem [1] https://en.m.wikipedia.org/wiki/American_flag_sort https://en.m.wikipedia.org/wiki/American_flag_sort

ipsum2 2y ago
First thing I think about with "rainbow" and "data structures" is rainbow tables.
blibble 2y ago
a double-ended queue is often implemented using a doubly linked list (like the one in use here) if you back it by two arrays then you can't do O(1) inserts in the middle (like is going on here)
- tialaramex 2y ago
  It's true that awful Deque implementations are often built from a linked list. If you're taught about big-O notation and haven't noticed how modern computers work you might even do that today. I would expect that they're thinking of something more like Rust's VecDeque, so that's a conventional "growable array" (Rust's Vec, Java ArrayList, C++ std::vector) used internally with some head + tail tracking to form a circular buffer so as to deliver the Deque API (fast push to head or tail, fast pop from head or tail).
  - blibble 2y ago
    you can make mechanically sympathetic linked lists with low constant factors as long as you avoid pointers

AutistiCoder 2y ago

so, I had ChatGPT give me a quick run through, after feeding it the JesseSort python file, here's how it understood the algorithm in simple terms: 1. It starts with two elements and places them in order. 2. Each new element is inserted into the correct position within the growing "rainbow" of sorted bands. 3. By the time all elements are inserted, the list consists of multiple sorted bands that are then merged. Was it wrong?

earnestinger 2y ago
Pdf mentions split rainbows

drpixie 2y ago

If you're going to make a big claim about sort speed, tell me how speed is better/worse for various data. How do the algorithms compare when the data is already ordered, when it's almost (but not quite) already ordered, when it's largely ordered, when it's completely random, and it's in the opposite order. This stuff, as well as the size of the dataset, is what we need to know in practice.

sambeau 2y ago
https://www.researchgate.net/publication/388955884_JesseSort https://www.researchgate.net/publication/388955884_JesseSort
- deleted 2y ago
  [deleted]
- nimih 2y ago
  What's your point? The paper you're linking does not include the analysis the post you're responding to is asking for.
  - gymbeaux 2y ago
    It does give some insight into what you seek, at least. For example, “We ﬁnd that for smallern≲262144, JesseSort is slower 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.
tialaramex 2y ago
Rather than, or at least in addition to, raw measured speed on a specific piece of hardware, which is often affected in hard to understand ways by niche optimisation choices and nuances of specific hardware, I actually really like the choice to report how many comparisons your algorithm needed. For example Rust's current unstable sort takes ~24 comparisons on average for each of 10^7 truly random elements to sort them all, but if instead all those elements are chosen (still at random) from only 20 possibilities, it only needs a bit more than five comparisons regardless of whether there are 10^3 elements or 10^7. Unlike "On this Intel i6-9402J Multi Wazoo (Bonk Nugget Edition) here are my numbers" which is not very useful unless you also have the i6-9402J in that specific edition, these comparison counts get to a more fundamental property of the algorithm that transcends micro architecture quirks which will not matter next year.

behnamoh 2y ago

I have mixed feelings about the naming. Isn't it kinda off-putting that he named it after himself? usually it's other people who name your algorithm after you. At least that's how it's like in science and engineering (Fourier didn't call it "Fourier transform", Laplace didn't call it "Laplace transform", Kalman didn't name it "Kalman filters", etc.)

gyudin 2y ago
Like Dijkstra's algorithm? Knuth-Morris-Pratt algorithm? Huffman coding?
- charlieyu1 2y ago
  Did any of these guys put their name on the algorithm by themselves?
  - vanderZwan 2y ago
    The author seems young, I think we should be a little forgiving if they saw all these algorithms and concluded "ok so if you come up with something new you get to name it after yourself"
- quuxplusone 2y ago
  Not to mention Shellsort. https://en.wikipedia.org/wiki/Donald_Shell https://en.wikipedia.org/wiki/Donald_Shell
- behnamoh 2y ago
  those names were given to those algorithms by others, not the creators.
  - gymbeaux 2y ago
    What did they call their algorithms before they passed away?

xiaodai 2y ago

Python's default is gallop sort however radixsort is much faster and performs in O(n).

ijustlovemath 2y ago
I thought it was Timsort?
- pstoll 2y ago
  It was and always will be timsort-ly yours. iykyk.
selcuka 2y ago
> radixsort is much faster and performs in O(n). Radix sort time complexity is not O(n); it's O(n*k) where k is the size of the largest element. Besides it has an additional O(n+k) space complexity.
perlgeek 2y ago
radixsort isn't a comparison-based sort algorithm, so you're comparing apples to chickens.

prirun 2y ago

"We ﬁnd that for smaller n≲ 262144, JesseSort is slower than Python’s default sort."

repsilat 2y ago
I wonder about the global statistics of sorted data... Is the most common number of elements to sort zero? Certainly less than ten? What about the median? Two elements to sort? One? Zero again?
- lblume 2y ago
  The question is also for which list lengths the performance matters most. When sorting a few strings (<20), whether the algorithm uses 5 or 7 comparisons would usually not matter too much. So to find the optimal algorithm for a given situation, we would have to compute a weighted average by list length importance on the performances of the algorithm per list length.
3eb7988a1663 2y ago
Don't high performance systems have heuristics to decide what specific algorithms to use at runtime? It is not unimaginable to think that there could be a function dedicated to small vs large collections. Assuming the results hold, someone has to decide if the additional complexity is worth the performance. For something like BLAS, go nuts. For Python standard library, maybe not.

agnishom 2y ago

I am a bit concerned that the primary channel of distribution of the paper is ResearchGate. I am somehow biased against taking it seriously because of this.

mlochbaum 2y ago

So the idea is that you'll eventually arrange n elements into ideally about √n sorted lists, organized so that the endpoints of these lists are also ordered (the "rainbow" shape). A new element goes on the end of one of those lists or a new list; which one is generally decided by binary search, but the index is saved to speed up the next insertion if it's the same. So a natural run might benefit by having adjacenct values inserted to the same list. Which cases benefit and which don't seems potentially quite erratic. If you have a series of runs that shrink over the course of the array, with increasing start value and decreasing start value, each will become a new sorted list and you end up with O(n) insertion plus a perfect merge. If the runs get wider instead, they'll cross over existing endpoints and end up spattered around before merging. It feels like the paper keeps trying to spin constant-factor improvements as somehow being asymptotically relevant despite acknowledging that mathematically they aren't, for example the fact that log(√n) is only log(n)/2 "would not reflect the sublinear nature of base array length k" and runs hitting the best case "approximately 50% of the time... reinforces JesseSort's average runtime complexity as somewhere between O(n) and O(n log_2 n)". Powersort provably takes O(n + n log r) worst-case time where r is the number of runs; I expect this algorithm is O(n log n) worst- and average-case. However, on random arrays the given benchmarks do improve relative to Python default as the length increases, with faster performance starting a little under a million elements. There isn't a lot of investigation into why this is. I'd be interested to know if the number of comparisons is reduced in particular. Perhaps this algorithm is more cache-friendly with a random input, but this wouldn't be reliable as many inputs can cause the number of sorted lists to scale with O(n) so that the binary searches need to work on a large array.

mlochbaum 2y ago
The analysis would make a lot more sense if it dropped every big O and computed an expected number of comparisons. Of course, the real issue is that the whole thing relies on an empirically-determined length of √8√n for the number of lists in the rainbow, when the theoretical justification isn't there and clearly the worst case is n/2. I'm not seeing any awareness that the expected number of comparisons has to be at least log_2(n!), and am starting to see some worrying signs that the author thinks averages like n log log n are possible. I'd initially assumed that "somewhere between O(n) and O(n log_2 n)" statement meant in the presence of asymptotically large natural runs, but there's a claim that the runs "need not be of any minimum size" and another that the algorithm can "capitalize on natural runs" that seems to be referring to the benchmarks on "purely random values".

ggm 2y ago

"This journal no longer accepts papers on optimal solutions to the 9 queens problem"

funnyAI 2y ago

[dead]

vivzkestrel 2y ago

I know it is not possible in our Universe but on a lighter note, in some parallel universe out there, someone has made a sorting algorithm that runs in O(1). I wonder though if a quantum computer can simultaneously sort all the elements in O(1)

warkdarrior 2y ago
"quantum computers are no better than classical ones [for sorting]" https://en.m.wikipedia.org/wiki/Quantum_sort https://en.m.wikipedia.org/wiki/Quantum_sort
procaryote 2y ago
If you can pick parallel universes, just pick the one where the data happens to be sorted
henry2023 2y ago
A modern Borges could write a really good short story about that universe.

tcper 2y ago

Amazing, there is still new sort algorithm today!

conradludgate 2y ago

And what about pdqsort, glidesort, driftsort, ipnsort? New research is always cool, but there's plenty of other research in this space to compare this to

tim-peters 2y ago

I want to elaborate on timing cautions: a sort that specializes to 4-byte machine ints is doing something that can't be expressed directly in CPython. Its lists are heterogeneous, types aren't known until runtime, and there is no native (to Python) concept of "4-byte int". All CPython ints are stored in "bigint" (unbounded) format, and even zero requires 32 bytes of storage in the format (overheads for a type pointer, refcount, 16-byte heap alignment padding). That format isn't 2's complement either (although it creates the semantic _illusion_ of being such): it's sign+magnitude. The general object comparison machinery is very expensive at runtime, essentially repeated from scratch on every compare. To mitigate this, CPython does a prepass over the list (O(n)) to see whether the list is in fact homogenous, and, if so, of a type that can use a more specialized comparison function. Not free, but pays off hugely if you are in fact sorting a list of "small enough" machine ints. But it doesn't change the storage format: on every compare, cycles are still consumed to transform CPython's sign+magnitude bigint format to native 2's-complement for native machine code to compare directly. I expect this accounts for most of the observed "speedup" over timsort. Despite semi-heroic efforts to cut the cost, comparisons of native ints in CPython will always be significantly more expensive than code specialized to compare native ints directly. At least until (if ever) CPython learns how to "unbox" ints. The PyPy implementation of Python already does, and sorting lists of native machine ints runs about twice as fast under PyPy. It's not the sorting algorithm that matters to this, it's the relative cost of machine-int compares, and almost certainly too the cache pressure of using many more bytes to store small ints than necessary in "boxed" format. As mentioned elsewhere, JesseSort reminds me most of the old and simpler "patience sorting", with which it has a lot in common. Both keep a collection of sorted sublists (to be merged at the end), both use binary search to pick a collection member to which to add 'the next" input, both excel at "low diversity" inputs, both (on average) end up with O(sqrt(n)) sublists on randomly ordered inputs, and neither is "naturally" stable. As I noted in listsort.txt at the time, while timsort gets a lot of value out of repeated elements ("low diversity"), it's just not the right approach to exploit that aa much as possible. JesseSort and pdqsort (and, by extension, glidesort) will always do better on that. OTOH, timsoet gets value out of many kinds of partial ordering, which "reveal themselves" dynamically via one run in a merge "winning" consistently.