[Python-3000] BList PEP
daniel at stutzbachenterprises.com
Wed May 2 05:17:04 CEST 2007
On 5/1/07, Terry Reedy <tjreedy at udel.edu> wrote:
> "Daniel Stutzbach" <daniel at stutzbachenterprises.com> wrote in message
> news:eae285400705010000l2af0e890ifc8c2e0de8219961 at mail.gmail.com...
> | Sort O(n log n) O(n log n)
> Tim Peters' list.sort is, I believe, better than nlogn for a number of
> practically important special cases. I believe he documented this in the
> code comments. Can you duplicate this with your structure?
The table in the PEP lists worst-case execution times. I'll make that
explicit in the next revision. You are correct that TimSort is O(n)
for nearly-sorted lists. It's possible to implement TimSort over the
BList, but I have not yet done so.
Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises LLC
More information about the Python-3000