On Mon, May 2, 2022 at 2:25 AM jan via Python-list <python-list@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. -- https://mail.python.org/mailman/listinfo/python-list
