[Python-3000] BList PEP

[Daniel Stutzbach]

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