Am 27.08.2011 09:40, schrieb Steven D'Aprano: > Terry Reedy wrote: >> On 8/26/2011 8:23 PM, Antoine Pitrou wrote: >> >>>> I would only agree as long as it wasn't too much worse >>>> than O(1). O(log n) might be all right, but O(n) would be >>>> unacceptable, I think. >>> >>> It also depends a lot on *actual* measured performance >> >> Amen. Some regard O(n*n) sorts to be, by definition, 'worse' than >> O(n*logn). I even read that in an otherwise good book by a university >> professor. Fortunately for Python users, Tim Peters ignored that >> 'wisdom', coded the best O(n*n) sort he could, and then *measured* to >> find out what was better for what types and lengths of arrays. So not >> we have a list.sort that sometimes beats the pure O(nlog) quicksort of >> C libraries. > > A nice story, but Quicksort's worst case is O(n*n) too.
In addition, timsort is O(n log n), which also makes it a real good O(n*n) sort :-) Regards, Martin _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
