efficient idiomatic queue?

James_Althoff at i2.com James_Althoff at i2.com
Thu Jan 17 21:28:40 CET 2002

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

Thanks for sharing this.  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).

<Tim Peters>
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
I expect it remains very hard to beat (for Python's
specific ratio of slow comparison to cheap object movement (just pointer
</Tim Peters>

On the list of 100,000 the builtin tim.list.sort was a mere 800x or so
faster than the generator version.

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.  :-(


<Tim Peters>
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
                    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
</Tim Peters>

More information about the Python-list mailing list