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
JesseSort: A novel sorting algorithm that is faster than Python's default sort.
41–50 of 65 posts
Re: JesseSort: A novel sorting algorithm that is faster than Python's default sort.
#42Earlier quoted context omitted.
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 circu…
you can make mechanically sympathetic linked lists with low constant factors as long as you avoid pointers
Do you mean using indices into a backing array instead of pointers if the maximum length is known to be small? That probabdy helps but still has the cache issue to some degree no?
(also I feel like this is arguing semantics a bit, but I'm sincerely wondering: is a linked list without pointers still a linked list?)
Re: JesseSort: A novel sorting algorithm that is faster than Python's default sort.
#43"We find that for smaller n≲ 262144, JesseSort is slower than Python’s default sort."
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.
Re: JesseSort: A novel sorting algorithm that is faster than Python's default sort.
#44Earlier quoted context omitted.
Like Dijkstra's algorithm? Knuth-Morris-Pratt algorithm? Huffman coding?
Did any of these guys put their name on the algorithm by themselves?
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"
Re: JesseSort: A novel sorting algorithm that is faster than Python's default sort.
#45Python's default is gallop sort however radixsort is much faster and performs in O(n).
radixsort isn't a comparison-based sort algorithm, so you're comparing apples to chickens.
Re: JesseSort: A novel sorting algorithm that is faster than Python's default sort.
#46I 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)
If you can pick parallel universes, just pick the one where the data happens to be sorted
Re: JesseSort: A novel sorting algorithm that is faster than Python's default sort.
#47I 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.)
I like the name.
Re: JesseSort: A novel sorting algorithm that is faster than Python's default sort.
#48So 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 v…
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…
Ah, the README prior to commit b98f724 does claim O(n log(1.5 ln(n))) asymptotic runtime. This is based on a flawed analysis assuming rainbow endpoints will be evenly distributed, which the paper presents before describing the problem that each inserted element pushes one of those endpoints away from the middle. Bit of a perpetual motion machine search: initial results showed the promise of this approach, some details got in the way but surely there's some trick to work around them...
Still there's the benchmark. I remembered timsort.txt shows comparison counts relative to the log_2(n!) bound and it's only like 1% worse, so the >30% improvement over Timsort at the high end has to come from some other factor. I'm thinking it is actually cache effects—not because the algorithm has inherently better cache properties, as it's just a merge sort at large scales, but because it copies the array to ints internally rather than using a generic comparison. That would be a poor result, as good comparison sorts compiled for 4-byte data are many times faster than Timsort.
Re: JesseSort: A novel sorting algorithm that is faster than Python's default sort.
#49I 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)
A modern Borges could write a really good short story about that universe.