test_sergio.py

import itertools
import random

def power_two(x):
	return x and (x & (x - 1) == 0)

def asort(A, i, j):
	assert power_two(j - i + 1), '%d - %d + 1 not power of 2' % (j, i)
	if A[i-1] > A[j-1]:
		A[i-1], A[j-1] = A[j-1], A[i-1]
	if i + 1 < j:
	    k = (j - i + 1) // 4
	    asort(A, i, j - 2*k)
	    asort(A, j - 2*k + 1, j)
	    asort(A, i + k, j - k)
	    asort(A, i, j - 2*k)
	    asort(A, j - 2*k + 1, j)
	    asort(A, i + k, j - k)

N = 16
for B in [(11,21,13,41,15,16,71,28,19,10,1,12,3,14,5,6)]:
	A = list(B)
	asort(A, 1, len(A))
	if A != sorted(B):
		print 'failed on', B
		print 'got', A
		assert False
	print B