efficient idiomatic queue?

[Tim Peters]

[James Althoff, on an "elegant" mergesort]
> is probably going to create way too many generator/iterator
> instances to scale well.

[Tim]
> Well, it was clear from the start that there's no interest in a
> practical algorithm here, else we'd just use a temp array and a
> handful of index variables.

[David Eppstein]
> I think heap sort would be a good choice for practicality, since it sorts
> in-place with only a handful of index variables.

Following is the spelling of mergesort I've had in mind ("a temp array and a
handful of index variables").  It's eminently practical.  Note that if the
list doesn't have an exact power-of-2 size, no attempt is made to "balance"
the excess across passes.  That keeps the code simple, but doesn't harm
correctness or O() behavior.  Better speedups can be obtained via simpler
means than balancing (like picking on the innermost loop, and splitting off
the first (s=1) pass to swap out-of-order pairs in-place directly).

def mergesort(A):
    "Sort list, via stable mergesort."
    n = len(A)
    B = [None] * n
    swapped = 0
    s = 1
    while s < n:
        s2 = s+s
        # Invariant:  viewing A as a sequence of slices of length s (plus
        # perhaps an oddball at the end), each slice is sorted.  (This is
        # trivially so when s=1; proceed by induction.)  Now merge adjacent
        # pairs of slices into sorted slices twice as large.
        for i in range(0, n, s2):
            ihi = j = i+s       # start of adjacent slice
            jhi = min(j+s, n)   # final slice may have an oddball size
            k = i               # start of output slice
            while i < ihi and j < jhi:
                if A[i] <= A[j]:
                    B[k] = A[i]
                    i += 1
                else:
                    B[k] = A[j]
                    j += 1
                k += 1
            # Copy tail.  At most one of these isn't vaccuous.
            B[k : k+ihi-i] = A[i : ihi]
            B[k : k+jhi-j] = A[j : jhi]
        # Swap input and output lists.
        A, B = B, A
        swapped = not swapped
        s = s2

    if swapped:  # copy back into original input list
        B[:] = A

This is easier to get right for most people than a heapsort, and, if you can
afford the memory hit for a temp vector, generally runs faster (esp. for
large arrays on VM machines -- this mergesort's sequential memory access
works much better with typical disks and OS paging policies than heapsort's
leaping around).  Coding is straightforward even in assembler.  It doesn't
lend itself to finding "just the first K" quicker, though.

> But except for unusual circumstances, I would likely just call Python's
> built-in sort().

That's at least sane <wink>.  I wrote Python's current list.sort(), and it
runs faster than the quickest mergesort I was able to code in C at the time
(which was a variant of the above, plus playing every low-level speed trick
under the sun).  The quickest mergesort was a little quicker than the
quickest quicksort I tried; heapsort wasn't competitive.  The sort() Python
ended up with is a nightmarish hybrid of single-thread samplesort and binary
insertion sort.  That was the clear winner out of about 20 sort
implementations, and I expect it remains very hard to beat (for Python's
specific ratio of slow comparison to cheap object movement (just pointer
copies)).

life-is-ugly-where-the-theory-collides-with-the-hw<wink>-ly y'rs  - tim