Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site ho95b.UUCP
Path: utzoo!watmath!clyde!burl!mgnetp!ihnp4!houxm!ho95b!wcs
From: wcs@ho95b.UUCP (59577)
Newsgroups: net.lang
Subject: Parallel Sorting - Shell ?
Message-ID: <169@ho95b.UUCP>
Date: Mon, 25-Jun-84 13:55:25 EDT
Article-I.D.: ho95b.169
Posted: Mon Jun 25 13:55:25 1984
Date-Received: Thu, 28-Jun-84 01:27:29 EDT
Organization: AT&T Bell Labs, Holmdel NJ
Lines: 12

Dave Seaman (ags@pucc-i) gave some timing results for optimal
sorts on parallel machines, citing Bubble, Insertion, and
Quicksort.  Shell-sort is an algorithm that looks inherently
designed for parallel operation; has anyone tried it on a
parallel machine?  While analysis of the algorithm is
complicated, it has an asymptotic performance of N**3/2 for a
simple implementation, and can be reduced to N*(log N)**2, with
a higher multiplicative constant, by doing some extra work.
-- 
				Bill Stewart
				AT&T Bell Labs, Holmdel NJ
				...!ihnp4!ho95b!wcs