Re:Changing std:sort at Google’s scale and beyond
by orlp on Wednesday April 20, 2022 @06:03PM
(#31103659)
> and for the other two points you are referring to particular extensions of quicksort
Maybe for the third point, but once again, every implementation does this. For the first point, absolutely not. Just because in-place partitioning is often the only variant described, out-of-place partitioning is absolutely just quicksort, not an extension.
> Quite possibly you can extend quicksort similar to how timsort extended mergesort
Please see my top comment in this thread - I have done exactly that. Or rather, I have extended powersort (which is very similar to timsort) with quicksort.
Maybe for the third point, but once again, every implementation does this. For the first point, absolutely not. Just because in-place partitioning is often the only variant described, out-of-place partitioning is absolutely just quicksort, not an extension.
> Quite possibly you can extend quicksort similar to how timsort extended mergesort
Please see my top comment in this thread - I have done exactly that. Or rather, I have extended powersort (which is very similar to timsort) with quicksort.