@TechReport{chaudhry:tricks,
  author = {Geeta Chaudhry and Elizabeth A. Hamon and Thomas H. Cormen},
  title = {Stupid Columnsort Tricks},
  year = {2003},
  month = {April},
  number = {TR2003-444},
  institution = {Dept. of Computer Science, Dartmouth College},
  address = {Hanover, NH},
  URL = {ftp://ftp.cs.dartmouth.edu/TR/TR2003-444.ps.Z},
  keywords = {parallel I/O, sorting, out-of-core applications, pario-bib},
  abstract = {Leighton's columnsort algorithm sorts on an $r \times s$ mesh,
  subject to the restrictions that $s$ is a divisor of~$r$ and that $r \geq
  2s^2$ (so that the mesh is tall and thin). We show how to mitigate both of
  these restrictions. One result is that the requirement that $s$ is a divisor
  of~$r$ is unnecessary; columnsort sorts correctly whether or not $s$
  divides~$r$. We present two algorithms that, as long as $s$ is a perfect
  square, relax the restriction that $r \geq 2s^2$; both reduce the exponent
  of~$s$ to~$3/2$. One algorithm requires $r \geq 4s^{3/2}$ if $s$ divides~$r$
  and $r \geq 6s^{3/2}$ if $s$ does not divide~$r$. The other algorithm
  requires $r \geq 4^{3/2}$, and it requires $s$ to be a divisor of~$r$. Both
  algorithms have applications in increasing the maximum problem size in
  out-of-core sorting programs.}
}