new sorting algorithm
Dan Stromberg
drsalists at gmail.com
Mon May 2 22:11:19 EDT 2022
On Mon, May 2, 2022 at 2:25 AM jan via Python-list <python-list at python.org>
wrote:
> Hi,
>
> > The median-of-three partitioning technique makes that work reasonably
> well, so it won't be pathologically slow
>
> Just to be clear because I've wondered but haven't looked into it, we
> know naive quicksorting of already-sorted data is pathalogical, but
> median-of-3 is known to fix this pathology?
>
Median-of-3 helps, but it's still possible to construct inputs that make
quicksort break down to an O(n^2) algorithm in the worst case. These
inputs are much less common than sorting an already sorted, or
reverse-sorted list.
More information about the Python-list
mailing list