[Python-3000] BList PEP

Daniel Stutzbach 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 mailing list