Show HN: I developed a fast general purpose sorting algorithm
github.com
github.com
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?
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).
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.
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.
* Comparing chensort with Arrays.parallelSort for an array with random values and chensort is slower on my machine * When using an array that contains a lot of duplicates, Arrays.sort is 30 times faster than chensort on my machine * When using an array that is almost sorted, Arrays.parallelSort is 2 to 3 times faster on my machine
Of course it's faster. And no it's not as general-purpose.
Unlike this post though, it's got proper comparisons against the best C implementations of other algorithms, and is aware that, as most inputs aren't entirely random, its use is very limited.
What about slowest?
The time complexity is O(n) at best and O(nlogn) at worst, the space complexity is O(n), and it is stable.
Randomly generate [1000,10000000] random numbers in the range [-2^63,2^63-1], average speed is 3 times faster than Quicksort, fastest is 20 times. Traditional counting sorts and bucket sorts cannot handle such a large range of values because the performance is worse than Quicksort.
In general, it makes most sense to compare it against allocating, distribution based sorts.
Additionally, with interpolation sorts, you have to be pretty careful that the interpolation is sufficiently well implemented to maximize overlapping inserts.
I don't see an official name, but I would also be curious to compare it to an interpolation variation on a library sort.
Other distributions are of interest. In particular, ones with high skew like various exponential ones and lognormal.
Examples:
https://opensource.googleblog.com/2022/06/Vectorized%20and%2... (2022)