Integer Sorting on a Mesh-Connected Array of Processors

Schnorr and Shamir and independently Kunde, have shown that sorting N =n superscript 2 inputs into snake-like ordering on a n X n mesh requires 3n -o(n) steps. Using a less restrictive, more realistic model we show that the sorting N = n superscript 2 integers in the range [1 ...N] can be performed in 2n +o(n) steps on a n X n mesh