Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!gatech!hubcap!Jonathan
From: jfbuss%water.waterloo.edu@RELAY.CS.NET (Jonathan Buss)
Newsgroups: comp.parallel
Subject: Re: Sorting on NxN Mesh.
Message-ID: <4249@hubcap.UUCP>
Date: 30 Jan 89 20:09:07 GMT
Sender: fpst@hubcap.UUCP
Lines: 6
Approved: parallel@hubcap.clemson.edu

See Schnorr and Shamir, "An optimal sorting algorithm for
mesh-connected computers," Eighteenth Ann. Symp. on Theory of
Computing (1986) p. 255.  They show that 3n steps is optimal, and
give a simple algorithm to achieve the bound.

Jonathan Buss