4 ms·
Related is samplesort https://de.wikipedia.org/wiki/Samplesort https://de.wikipedia.org/wiki/Samplesort - it is a comparison sort, and yes the complexity is als
by thomasmg 7y ago
Related is samplesort https://de.wikipedia.org/wiki/Samplesort https://de.wikipedia.org/wiki/Samplesort - it is a comparison sort, and yes the complexity is also O(n log n), same as quicksort and merge sort. But it may have less branches, and possibly better cache locality. It is stable btw. Disadvantage: it uses a O(n) memory.
I made some experiments with samplesort, and found with Java it can be about 40% faster than Arrays.sort, and for C++ maybe 5-10% faster: https://github.com/thomasmueller/fastSort_java https://github.com/thomasmueller/fastSort_java and https://github.com/thomasmueller/fastSort_cpp https://github.com/thomasmueller/fastSort_cpp
- twic 7y agoOh yes, i've basically reinvented samplesort! Fifty years too late, sadly.
- thomasmg 7y agoWell, the same thing happened to me. I implemented it, wrote a benchmark, and later was told this is samplesort... Historic footnote: samplesort was the Python sort algorithm before it was replaced with Timsort: https://bugs.python.org/issue587076 https://bugs.python.org/issue587076 (specially see the attached timsort.txt)
- wnoise 7y agoIn English: https://en.wikipedia.org/wiki/Samplesort https://en.wikipedia.org/wiki/Samplesort