Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!gatech!hubcap!halldors
From: halldors@athos.rutgers.edu (Halldorsson)
Newsgroups: comp.parallel
Subject: Re: Sorting on NxN Mesh.
Message-ID: <4298@hubcap.UUCP>
Date: 2 Feb 89 18:31:26 GMT
Sender: fpst@hubcap.UUCP
Lines: 47
Approved: parallel@hubcap.clemson.edu

I wrote:

> Preliminary, empirical investigation of the problem indicates that the
> algorithm given is linear.  I conjecture a 6n upper bound
> (cmp-xchg, or 12n routing operations).

Unfortunately, this has turned out not to be true. The algorithm has a
worst case complexity of O(n^2).
   Consider these two kinds of input:

1) Fill the upper triangular matrix of 1's, and the lower of 0's.

               1 1 1 1 1 1 1 1
               0 1 1 1 1 1 1 1
               0 0 1 1 1 1 1 1
               0 0 0 1 1 1 1 1
               0 0 0 0 1 1 1 1
               0 0 0 0 0 1 1 1
               0 0 0 0 0 0 1 1
               0 0 0 0 0 0 0 1

The algorithm sorts it in  n^2/2 + 3n cmp-xchg operations.

2) Divide the columns into four sections, fill the middle two with
1's, and the left and the right sections with 0's.

               0 0 1 1 1 1 0 0
               0 0 1 1 1 1 0 0
               0 0 1 1 1 1 0 0
               0 0 1 1 1 1 0 0
               0 0 1 1 1 1 0 0
               0 0 1 1 1 1 0 0
               0 0 1 1 1 1 0 0
               0 0 1 1 1 1 0 0

The algorithm will sort it in  n(n+1)/2 + 4  cmp-xchg operations.

> It runs consistently in around 5n parallel
> compare-exchange (cmp-xchg) operations. 

That is true, and the average case appears to be somewhere between 4n
and 5n, hence the algorithm might actually be quite useful in practice.

Magnus

Note: These results have been gotten by simulation. They have not been
      proven.