# 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
a
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
<snip>
I expect it remains very hard to beat (for Python's
specific ratio of slow comparison to cheap object movement (just pointer
copies)).
</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.  :-(

Jim

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

```