Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Fastest parallel Sort
0 views
Skip to first unread message
Ned Horvath
Jun 18, 1984, 4:21:16 PM6/18/84
to
The fastest known parallel sort uses the Batcher net and operates in time
O((log n)^2). That is also known to be optimal for a general (i.e. not
data-dependent) sorting algorithm. As usual, see Knuth, v. 3, for details.
O((log n)^2). That is also known to be optimal for a general (i.e. not
data-dependent) sorting algorithm. As usual, see Knuth, v. 3, for details.
=Ned=
LIPINSKI
Jun 21, 1984, 11:57:17 PM6/21/84
to
The fastest parallel sort has recently been proved to be O(log n),
which improves upon Batcher's O((log n)^2). It's in a paper by
Komlos, Ajtai, and Sar??? (sp) [Stanford &/| UCSD], and it uses
expander graphs and a linear nearsort algorithm. The problem is
that the linear coefficient is huge (10^20?), so it's no good to
actually implement it; it just proved it can be done in O(log n).
which improves upon Batcher's O((log n)^2). It's in a paper by
Komlos, Ajtai, and Sar??? (sp) [Stanford &/| UCSD], and it uses
expander graphs and a linear nearsort algorithm. The problem is
that the linear coefficient is huge (10^20?), so it's no good to
actually implement it; it just proved it can be done in O(log n).
Michael Baldwin
{harpo,ihnp4}!whuxg!mike
0 new messages