Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!gatech!hubcap!Dan
From: dan@csun1.cs.uga.edu (Dan Gordon)
Newsgroups: comp.parallel
Subject: Re: Sorting on NxN Mesh.
Message-ID: <4250@hubcap.UUCP>
Date: 30 Jan 89 20:09:19 GMT
Sender: fpst@hubcap.UUCP
Lines: 23
Approved: parallel@hubcap.clemson.edu

In article <4225@hubcap.UUCP> halldors@paul.rutgers.edu (Magnus M Halldorsson) writes:
>Preliminary, empirical investigation of the problem indicates that the
>algorithm given is linear. It runs consistently in around 5n parallel
>compare-exchange (cmp-xchg) operations. I conjecture a 6n upper bound
>(cmp-xchg, or 12n routing operations).
>

Similar algorithms have been looked at before, sorting on a mesh by alternately
sorting in rows and columns (although in these, one step usually consists
of completely sorting a row or column using the odd-even transposition sort,
not just doing one transposition).  The most recent reference is an article
by Marberg and Gafni in Algorithmica last year.

I'd be surprised if your conjecture is correct.  Most such algorithms end
up at least a factor of log n below optimal.  Marberg and Gafni gave an
algorithm which sorted in O(n) steps, but it required several new ideas to
achieve that.  I recently wrote a paper which analyzes the same type of
algorithm on a 2^n hypercube, where it requires O(log^2 n) time, also
a factor of log n worse than optimal

Dan Gordon
Depts. of CS and Math
University of Georgia