5 ms·

Sorting is not a niche topic. Anybody who majored in CS (which is a ton of people these days) will read the abstract and most of the paper thinking "Wow, I can'

by bloppe 3y ago

Sorting is not a niche topic. Anybody who majored in CS (which is a ton of people these days) will read the abstract and most of the paper thinking "Wow, I can't believe they discovered something better than O(N log N)" because that's usually what people mean when they say "better sorting algorithm". What they discovered here is effectively a new compiler optimization. They should present it as such instead of calling it a new sorting algorithm. But ya, discovering a new compiler optimization automatically is kinda cool.

qumeric 3y ago
Tbh people who majored in CS are supposed to know that it was proven long ago that better than O(N log N) sorting (in general case) is impossible.
elcomet 3y ago
I hope people majoring in CS will not think that, as they learned that n log n is the theorically best complexity for a sort algorithm. They will rather think that they found an algorithm with better constants in front of n log n.
- Zacharias030 3y ago
  true that
recursive 3y ago
70% better than O(N log N) is still O(N log N).
- ummonk 3y ago
  It's 70% better than O(1). The algorithms it found are for sort3, sort4, and sort5, which were poorly optimized in LLVM's libc++.
  - pclmulqdq 3y ago
    It may have also laundered those from open-source code that wanted to optimize sort3, sort4, and sort5.
saiojd 3y ago
I see your point. I just went over the abstract again and I totally agree.
Dylan16807 3y ago
> because that's usually what people mean when they say "better sorting algorithm" Is it really? I've heard of a few "better sorting algorithms" and it's never meant that in my experience.
- cubefox 3y ago
  When people say "sorting algorithm" they mean something like bubble sort or merge sort.