Path: utzoo!utgpu!attcan!uunet!lll-winken!ames!ncar!mailrus!uflorida!gatech!hubcap!halldors
From: halldors@paul.rutgers.edu (Magnus M Halldorsson)
Newsgroups: comp.parallel
Subject: Re: Sorting on NxN Mesh.
Message-ID: <4225@hubcap.UUCP>
Date: 27 Jan 89 20:19:33 GMT
Sender: fpst@hubcap.UUCP
Lines: 14
Approved: parallel@hubcap.clemson.edu

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).

This is quite good for such a simple algorithm. I am surprised of not
having seen this algorithm in the literature, despite a fairly
exhaustive search. Has somebody seen it before?

However,it is nowhere near optimal, especially considering that it
requires alternating comparisons (odd rows sort left-right, even rows
right-left).

Magnus