4 ms·
> The world's fastest general purpose sorting algorithm, 60% faster than Quicksort that's a pretty strong claim with essentially nothing to back it up. First
by ascar 4y ago
> The world's fastest general purpose sorting algorithm, 60% faster than Quicksort
that's a pretty strong claim with essentially nothing to back it up.
First off, the project is written in Dart & Java. I would expect an algorithm to be written in C for performance evaluation and comparison with other algorithms.
The only comparison provided is with Java's built-in `Array.sort`, which is a single threaded version, while his Java implementation is stated to be multi-threaded. The comparison thus is pretty useless. Especially since there is no mention of the used test architecture/hardware and available threads.
The only benchmark provided is for randomly generated integers. It lacks comparisons for many important corner cases like pre-sorted arrays, reverse-sorted arrays or arrays with tons of duplicates.
His benchmark output states 3x faster and 66% faster. That makes no sense! I guess what he wants to express is that his code runs 3x faster (e.g. 9000ms/3000ms) than the compared code and the runtime is 34% of the compared codes runtime (e.g. 3000ms/9000ms).
I do like that in his profile picture on GitHub he labels himself "Fake Experts" :)
> Currently writing an academic paper and expecting to be recognized by the academic community.
Well, good luck with that I guess?
- mr_gibbins 4y agoBold claim. If true, I would like to see the academic paper which I expect would contain the big-O time complexity, an explicit comparison to e.g. quicksort, and a general-purpose algorithm. If the sort is multi-threaded then this needs to be run as single-threaded as the item under test here is the algorithm, not how many cores it can be spun out to simultaneously (since many other sorts can be multi-threaded too).
- rowanG077 4y agoA multi threaded sort which beats the status quo is still very interesting.
- sshine 4y agoIn that case, he should compare this parallel sorting function to a parallel quicksort and a parallel mergesort. Once one iteration of QC’s partition function is run, you have distinct sub-problems on each side of the pivot element. Similarly, mergesort starts out with parallelisable sub-problems; merging collapses the parallelism gradually.
- zeusk 4y agoAlso, I don't see any actual tests verifying the output is correct. Gist of the algorithm seems to be classify numbers into buckets based on their factor of range (min, max values), then sort each bucket recursively if greater than 1000 elements or use conventional sorts before serially combining all the buckets for the result.