Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!rutgers!ucsd!sdcsvax!ucsdhub!hp-sdd!ncr-sd!ncrcae!hubcap!halldors
From: halldors@athos.rutgers.edu (Halldorsson)
Newsgroups: comp.parallel
Subject: Re: Sort on a NxN Processor Array
Message-ID: <4273@hubcap.UUCP>
Date: 1 Feb 89 13:18:45 GMT
Sender: fpst@hubcap.UUCP
Lines: 38
Approved: parallel@hubcap.clemson.edu

In article <4259@hubcap.UUCP> fpst@hubcap.UUCP (Steve Stevenson) writes:

> I have seen the (OETS) algorithm called 
> "Conways Algorithm" in a few journal articles dealing with formalism
> in the form of parallel touring machines, but I cannot trace the
> reference. If anyone has references to (OETS) or Conway, please send
> it on.

If you are referring to the aforementioned mesh version of OETS, then
I'm very interested in seeing those.

If you are referring to the plain OETS (also called "Brickwall sort"),
then Knuth vol.III discusses it, but I believe it originates with
Demuth:
   Demuth: "Electronic Data Sorting". Ph.D. Dissertation, 1956.
   Reprinted in IEEE TOC c-34,April 1985, pp.296

It is also discussed fairly well in these overview references:
  Akl: "Parallel Sorting Algorithms". (Wiley?) 1985

  Lakshmivarahan et al: "Parallel Sorting Algorithms", in Advances in
  Computers, 1984.

  Kronsjo: "Computational Complexity of Sequential and Parallel
Algorithms". Wiley 1985.

> Back to the references...

Good list of references. I can only add two more on mesh sorting:

  Kunde: "Routing&Sorting on Mesh-Connected Arrays", VLSI Algorithms &
  Architecture. Springer LNCS #319

  Leighton: "Tight Bounds on the Complexity of Parallel Sorting". STOC '84
	 Also in IEEE TOC, c-34, 4, April 1985, pp.344


Magnus