Re:Quadsort: a stable non-recursive merge sort
by mcherm on Friday February 14, 2020 @06:08AM
(#22325609)
No one is claiming that this sort algorithm (or any other) is asymptotically faster than O(n log(n)). It can be mathematically proved that no sort algorithm can improve on this. The object with sort algorithms is to find one with good constant-factor performance on typical inputs.
Frankly, I am more persuaded by the arguments in favor of an algorithm like "Tim-sort", which doesn't claim to micro-optimize hardware more efficiently (that's basically what "better swapping" is claiming), but instead claims that the algorithm is particularly efficient on some commonly-seen patterns (like "partially-sorted", or "pieces of the list are reverse-sorted"). Of course, any kind of argument about why one sort is better than another are inferior to actual benchmarks.
Re:Quadsort: a stable non-recursive merge sort
by davuinci on Friday February 14, 2020 @07:35AM
(#22326018)
To be precise, we can prove that no sort comparison-based algorithm can do better than O(n log(n)) comparisons. There are some variations though that do better than that, though they are not based on comparisons (i.e counting sort, radix sort).
Re:Quadsort: a stable non-recursive merge sort
by amcsi on Friday February 14, 2020 @07:16AM
(#22325941)
I'm quite a noob, and this is a bit off-topic, but if it's mathematically proven that no sorting algorithm can be faster then O(n*log(n)), but we know for sure that checking if an array is sorted is O(n), then doesn't that prove that P ≠ NP?
1000000 is peanuts. We need to see convergence for about billions+ of numbers.