4 ms·
Bold 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, a
by mr_gibbins 4y ago
Bold 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.