Stupid Columnsort Tricks
Geeta Chaudhry, Thomas H. Cormen · 2003
Leighton’s columnsort algorithm sorts on an r × s mesh, subject to the restrictions that s is a divisor of r and that r ≥ 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 ≥ 2s 2; both reduce the exponent of s to 3/2. One algorithm requires r ≥ 4s 3/2 if s divides r and r ≥ 6s 3/2 if s does not divide r. The other algorithm requires r ≥ 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. The columnsort algorithm presented by Leighton in 1985 [Lei85] sorts N values on an r × s mesh, where rs = N, subject to three restrictions: 1. r must be even, 2. s must be a divisor of r (the divisibility restriction), and