efficient idiomatic queue?

[Kragen Sitaker]

David Eppstein <eppstein at ics.uci.edu> writes:
> I think heap sort would be a good choice for practicality, since it sorts 
> in-place with only a handful of index variables.  But except for unusual 
> circumstances, I would likely just call Python's built-in sort().

That's good --- I was beginning to think you were delusional.

Even with hacks to make it less likely to hit its worst-case, though,
quicksort's constant factor makes it about twice as fast as mergesort.
How does heapsort's constant factor compare with mergesort's?

Python's built-in sort() uses quicksort (using a linear congruential
generator to pick pivot elements) to partition the array into small
chunks, and then uses an algorithm that looks a lot like a bubble sort
to sort the small chunks.  It has special cases for already-sorted
data, all-the-same data, reverse-sorted data, and each of the above
followed by some unsorted data.  This is the kind of thing you get
when you aim for practicality.