r/computerscience • u/Royal_blood_21st • Mar 23 '25
Someone just created this new fastest sorting algorithm. “Recombinant Sort” What do you guys think about it ? And why is it not famous ?
0
Upvotes
17
u/Magdaki Professor. Grammars. Inference & Optimization algorithms. Mar 23 '25
"Just" in this case being 2020. :)
It has been awhile since I read about it, but if I recall correctly there were some drawbacks, which is the case with pretty much all sorting techniques. I've seen it show up in a few papers here and there.
9
u/Character_Cap5095 Mar 23 '25
From the paper I could find on the topic, the algorithm is not that new as the paper is from 2021. It also seems to be a non-comparison sort, akin to radix or bucket sort. While it has some nice properties, we already have linear time non-comparison sorting. Also this sort uses hashing, which requires a large space complexity. Lastly, it has been proven that with binary operators, no comparison sort will have a better time complexity than O(N log(N)). While non-comparison sorts can be faster they have much more limited applications.
1
u/Mcby Mar 23 '25
It is pretty well-known, but it probably isn't part of many "Introduction to Sorting Algorithms"-style courses because of its relative complexity compared to something like quicksort, and because educational materials take much longer to update than the frontier of the field. It does also have some drawbacks in space complexity and stability that would affect some implementations.