Pseudosort a list in 2*n comparisons
Python, 7910 (7704 + 206)
This was inspired by shell sort. I found relatively good coefficients for the gap sequence (g
) by checking a few hundred alternatives. The number of comparisons is limited by counting explicitly (n
).
s=1
while s:
s=map(int,raw_input().split());k=len(s);n=2*k;g=13*k/23
while g:
for i in range(g,k):
n-=1
if n<0:break
if s[i]<s[i-g]:s[i],s[i-g]=s[i-g],s[i]
g=3*g/5
print' '.join(map(str,s))