In article <[EMAIL PROTECTED]>, Tim Peters <[EMAIL PROTECTED]> 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 ([EMAIL PROTECTED]) -- http://mail.python.org/mailman/listinfo/python-list
