throopw@rtp47.UUCP (Wayne Throop) (06/24/85)
A recent posting refered to a "constant time sort using n processors". Given comparison sorting, even using n processors to sort n items, it seems that it would require O(logN) time, not constant time. Am I right, or am I forgetting something? -- Wayne Throop at Data General, RTP, NC <the-known-world>!mcnc!rti-sel!rtp47!throopw
debray@sbcs.UUCP (Saumya Debray) (06/29/85)
Wayne Throop: > A recent posting refered to a "constant time sort using n processors". > Given comparison sorting, even using n processors to sort n items, it > seems that it would require O(logN) time, not constant time. Am I > right, or am I forgetting something? > You're right. In fact, most parallel sort algorithms that have been suggested (e.g. by Batcher, by Thompson & Kung) on common configurations like broadcast-bus networks, the butterfly, the shuffle-exchange network, grid networks etc., take O( log^2(N) ) time. A recent paper by Ullman cites an algorithm by Ajtai that takes O(log N) time on a broadcast-bus network, (though with very high overhead!). I should point out that these algorithms assume a fixed order of the nodes, p1 ... pN, independent of the elements at the nodes, and take "sort" to mean that the largest element has to be brought to p1, the next largest to p2, and so on. -- Saumya Debray SUNY at Stony Brook uucp: {allegra, hocsd, philabs, ogcvax} !sbcs!debray arpa: debray%suny-sb.csnet@csnet-relay.arpa CSNet: debray@sbcs.csnet