[Python-3000] BList PEP (original) (raw)
Daniel Stutzbach daniel at stutzbachenterprises.com
Wed May 2 05:17:04 CEST 2007
- Previous message: [Python-3000] BList PEP
- Next message: [Python-3000] PEP: Eliminate __del__
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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
- Previous message: [Python-3000] BList PEP
- Next message: [Python-3000] PEP: Eliminate __del__
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]