efficient idiomatic queue?

[Tim Peters]

[Tim]
>> Following is the spelling of mergesort I've had in mind ("a temp array
>> and a handful of index variables").  It's eminently practical.

[James Althoff]
> Thanks for sharing this.

Wait until you get the bill <wink>.

> I tried it on a list of 100,000 ints in reverse order.  It ran about
> 4.5x faster than the generator version (the generator-with-list.append
> version was a little faster than the all-generator version).

Note that it was written for clarity rather than speed; commentary in the
original post suggested two effective ways to speed it up; anyone obsessed
with speed will think of others.

[on the builtin list.sort()]
> On the list of 100,000 the builtin tim.list.sort was a mere 800x or so
> faster than the generator version.

I'm afraid that wasn't "a fair" comparison:  assuming you were still using a
list of 100,000 ints "in reverse order", list.sort() manages to sort
reverse-sorted inputs in linear time, while mergesort is always (best case
and worst case) N log N.  A fairer test would apply random.shuffle() to the
input first.  Note that if the "split off the s=1 iteration" suggestion for
speeding the mergesort is taken, it's easy to add a bit of code to the
split-off first iteration to detect already-sorted and
already-reverse-sorted in mergesort too (count how many swaps are done in
the split-off first iteration; a result of either 0 or total-number-of-pairs
is astronomically unlikely for random input, so if either obtains and
already-sorted or already-reverse-sorted are plausible input cases, it's
worth doing (at most) another n/2 compares to finish the job in linear time
when you can).

> The bad news -- for us Jython users -- is that on the list of 100,000
> Jython.list.sort was about 45x slower than cpython.list.sort.  :-(

Last I looked, Java used a quicksort.  In the common median-of-3 variant of
quicksort, reverse-sorted input is one of the best cases, but it's still an
N log N case.  Again it would be fairer to shuffle the input first.  The
thing that hurts quicksort for use in Python is that it does significantly
more comparisons (on average) than the theoretical minimum (on average), and
comparison of Python objects is a long-winded OO adventure <wink>.