Large Dictionaries

[Tim Peters]

[Jim Segrave]
> Actually, presorted lists are not a bad case for heapsort - it's quite
> immune to any existing order or lack thereof,

Write a heapsort and time it.  It's not a difference in O() behavior,
but more memory movement is required for a sorted list because
transforming the list into a max-heap at the start requires shuffling
the largest elements from the end of the list to its start.  Initially
reverse-sorted is a "good case" for heapsort in the same sense
(because the list is already a max-heap then; initially sorted is as
far from being a max-heap as is possible).  "good" and "bad" are both
O(N log N) here, though.

BTW, most people have never heard of Smoothsort, which was Dijkstra's
excruciating attempt to make heapsort exploit pre-existing order:

    http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796.PDF

That's one of a hundred algorithms I rejected for Python ;-)

> whereas some other sorts, quicksort being a prime example, require
> great care to avoid pathological cases.

Indeed, Python gave up on quicksort for that reason.  While the
samplesort hybrid that came between quicksort and the current sort
also had theoretical O(N**2) worst-case behavior, it was exceedingly
difficult to create such an input, and (unlike as for every quicksort
variant Python tried) no real-life case of undue sloth was ever
reported against it.