The best choice for this algorithm (according to its theoretical analysis, if not in practice) is the sorting network of . This can be interpreted as a PRAM algorithm in which the number P of processors is proportional to the input length n, and the number of parallel steps is logarithmic. Thus, simulating this algorithm sequentially takes time O(n\log n) for the simulation itself, together with O(\log n) batches of comparisons, each of which can be handled by O(\log n) calls to the linear-time decision algorithm. Putting these time bounds together gives O(n\log^2 n) total time for the parametric search. This is not the optimal time for this problem – the same problem can be solved more quickly by observing that the crossing time of the median equals the median of the crossing times of the particles – but the same technique can be applied to other more complicated optimization problems, and in many cases provides the fastest known strongly polynomial algorithm for these problems.
