Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

31–40 of 65 posts

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

#31

Post by blibble »

tialaramex wrote: post #27
blibble wrote: post #9

Earlier quoted context omitted.

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)

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

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

#33

Post by mlochbaum »

mlochbaum wrote: post #29

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 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 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".

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

#34

Post by vivzkestrel »

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)

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

#35

Post by repsilat »

prirun wrote: post #23

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

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?

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

#36

Post by [deleted] »

behnamoh wrote: post #12

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.)

[deleted]

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

#37

Post by warkdarrior »

vivzkestrel wrote: post #34

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)

"quantum computers are no better than classical ones [for sorting]"

https://en.m.wikipedia.org/wiki/Quantum_sort

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

#38

Post by arduanika »

bluepnume wrote: post #15
behnamoh wrote: post #12

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.)

He should have at least called it eejss-sort

This guy sorts

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

#39

Post by lblume »

repsilat wrote: post #35
prirun wrote: post #23

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

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?

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.
Post reply on HN