On Jan 27, 4:16 pm, Jonathan Gardner <jgard...@jonathangardner.net> wrote: > On Jan 27, 3:54 pm, Paul Rubin <no.em...@nospam.invalid> wrote: > > > Steven D'Aprano <ste...@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 -- http://mail.python.org/mailman/listinfo/python-list
