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&lt;0:break
   if s[i]&lt;s[i-g]:s[i],s[i-g]=s[i-g],s[i]
  g=3*g/5
 print' '.join(map(str,s))