3 ms·

I don't understand why you would need Timsort. If the pivot element is chosen randomly, Quicksort is always (or with probability bordering on certainty) O(n log

by chkas 4y ago

I don't understand why you would need Timsort. If the pivot element is chosen randomly, Quicksort is always (or with probability bordering on certainty) O(n log n). Update: I confused Timsort with IntroSort. I should have googled before posting ...

masklinn 4y ago
> I don't understand why you would need Timsort. If the pivot element is chosen randomly, Quicksort is always (or with probability bordering on certainty) O(n log n). For starters, it's a stable sort, which excludes quicksort right out the gates. Second, the primary hypothesis of timsort is that real-world data is non-random, timsort is biased for partially or almost-sorted sequences, which it can sort in as low as O(n). That would be the point westurner was making, timsort's creation is very much predicated on "really benchmark sorts on different data patterns". Third, for very short sequences (also a common situation) it's an insertion sort, which is extremely efficient due to the low overhead (even more so combined with the adaptivity which insertion sort also has).
- orlp 4y ago
  > For starters, it's a stable sort, which excludes quicksort right out the gates. Negative, it excludes in-place quicksort but out-of-place quicksort can be stable just fine. > Third, for very short sequences (also a common situation) it's an insertion sort, which is extremely efficient due to the low overhead (even more so combined with the adaptivity which insertion sort also has). Every modern quicksort implementation also does this (or a similarly efficient smallsort).
  - superjan 4y ago
    Hi, you are ignoring the second point, and for the other two points you are referring to particular extensions of quicksort. Quite possibly you can extend quicksort similar to how timsort extended mergesort, but if that was commonplace nobody would care about timsort.
    - orlp 4y ago
      > 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.

by chkas 4y ago

masklinn 4y ago

> I don't understand why you would need Timsort. If the pivot element is chosen randomly, Quicksort is always (or with probability bordering on certainty) O(n log n). For starters, it's a stable sort, which excludes quicksort right out the gates. Second, the primary hypothesis of timsort is that real-world data is non-random, timsort is biased for partially or almost-sorted sequences, which it can sort in as low as O(n). That would be the point westurner was making, timsort's creation is very much predicated on "really benchmark sorts on different data patterns". Third, for very short sequences (also a common situation) it's an insertion sort, which is extremely efficient due to the low overhead (even more so combined with the adaptivity which insertion sort also has).

orlp 4y ago
> For starters, it's a stable sort, which excludes quicksort right out the gates. Negative, it excludes in-place quicksort but out-of-place quicksort can be stable just fine. > Third, for very short sequences (also a common situation) it's an insertion sort, which is extremely efficient due to the low overhead (even more so combined with the adaptivity which insertion sort also has). Every modern quicksort implementation also does this (or a similarly efficient smallsort).
- superjan 4y ago
  Hi, you are ignoring the second point, and for the other two points you are referring to particular extensions of quicksort. Quite possibly you can extend quicksort similar to how timsort extended mergesort, but if that was commonplace nobody would care about timsort.
  - orlp 4y ago
    > 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.