wcs@ho95b.UUCP (59577) (06/25/84)
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