python 3's adoption

[Carl Banks]

On Jan 27, 4:16 pm, Jonathan Gardner <jgard... at jonathangardner.net>
wrote:
> On Jan 27, 3:54 pm, Paul Rubin <no.em... at nospam.invalid> wrote:
>
> > Steven D'Aprano <ste... at REMOVE.THIS.cybersource.com.au> writes:
> > > always much better written with key rather than cmp: key adds an O(N)
> > > overheard to the sorting, while cmp makes sorting O(N**2).
>
> > Whaaaaaaaaaa ...... ????  No I don't think so.
>
> You're referring to the O(N**2) bit, right? I am sure he knew it was O
> (N*log(N)), which is still worse than O(N) for key.
>
> If he didn't, well, Python has some fundamental flaws in its basic
> sort algorithm.

Quicksort is O(N**2) worst case, perhaps that's what he meant.  I'm
not sure about timsort but since it's based on quicksort I'd guess it
is O(N**2) or worse, worst case, as well.

Typical case of a sort is still O(N*log(N)) whether using key or cmp.
People recommended against cmp not because of overall algorithmic time
considerations, but because of the number of function calls.  cmp
function was called a minimum of N-1 times and typically around N*log2
(N) times, whereas key was called exactly N times.  Since the overhead
of a Python function call was very large compared to the built-in cmp
operation, it usually outweighed the algorithmic time considerations.


Carl Banks