Large Dictionaries

[Jim Segrave]

In article <mailman.6554.1149519174.27775.python-list at python.org>,
Tim Peters <tim.peters at gmail.com> wrote:
>[Scott David Daniels]
>>> For example, time timsort (Python's internal sort) on pre-sorted
>>> data; you'll find it is handled faster than random data.
>
>O(N) vs O(N log N), in fact.
>
>[Lawrence D'Oliveiro]
>> But isn't that how a reasonable sorting algorithm should behave? Less
>> work to do if the data is already sorted?
>
>For example, the O(N log N) heapsort is unreasonable compared to the
>O(N**2) bubblesort by that reasoning (pre-sorted is actually a bad
>case for heapsort, but a good case for bubblesort)?  O(N log N)
>sorting algorithms helped by pre-existing order are uncommon, unless
>they do extra work to detect and exploit pre-existing order.

Actually, presorted lists are not a bad case for heapsort - it's quite
immune to any existing order or lack thereof, whereas some other
sorts, quicksort being a prime example, require great care to
avoid pathological cases.



-- 
Jim Segrave           (jes at jes-2.demon.nl)