wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (02/22/90)
``Deterministic Sorting in Nearly Logarithmic Time on
the Hypercube and Related Computers.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
ALGORITHMS SEMINAR
-Monday, February 26, 1990
Dr. G. Plaxton, MIT Computer Science Lab will speak on
``Deterministic Sorting In Nearly Logarithmic Time on
the Hypercube and Related Computers.''
TIME: 3:30 p.m.
ROOM: DC 1304
ABSTRACT
This talk will present a deterministic sorting
algorithm, called Sharesort, that sorts n records on an
n processor hypercube, shuffle-exchange or cube-
2
connected cycles in O(logn(loglogn) ) time in the worst
case. The algorithm requires only a constant amount of
storage at each processor. The fastest previous
deterministic algorithm for this problem was bitonic
2
sort [Batcher~68], which runs in O(log n) time.
Joint work with Bob Cypher of IBM Almaden.