Algorithm Sketch
Algorithm: T rounds of O(1) time each
In round, process
groups of m vals, v1, v2,
, vm
Fill m
memory locations x1, x2,
, xm with 1
For
each 1£i,j
£m a
processor tests ...
if vi < vj then xi = 0 else xj = 0
If xk = 1 its max of group; pass xk to next round
The trick is to pick m right to
minimize T