new sorting algorithm

[Dan Stromberg]

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.