Slowing down sorting networks to obtain faster sorting algorithms

Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. This paper provides a general method that trims a factor of O (log n ) time (or more) for many applications of this technique.