simulation theory - how is the sorting only log(p)?

Question

In the proof of simulation theory : simulating concurrent write : "a p-processors in a crcw algorithm can be no more then log(p)time faster then the best erew algorithm for the same problem"

can anyone explain me why it takes only log(p) to sort the array by the first component in the simulation proof and not O(plogp)?

Answer 1

The sorting is accomplished in parallel with a log-depth sorting network. The AKS construction is a good example of a galactic algorithm. Batcher's bitonic sorting network with depth log^2 n is more reasonable in practice.