21–30 of 65 posts
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.)
Like Dijkstra's algorithm? Knuth-Morris-Pratt algorithm? Huffman coding?
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.
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.
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.
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 the…
Python's default is gallop sort however 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.
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.or…
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)
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).
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.)
Like Dijkstra's algorithm? Knuth-Morris-Pratt algorithm? Huffman coding?
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.