Concentrated regular data streams on grids: sorting and routing near to the bisection bound

Sorting and routing on r-dimensional n×. . .×n grids of processors is studied. Deterministic algorithms are presented for h-h problems, h⩾1, where each processor initially and finally contains h elements. It is shown that the classical 1-1 sorting can be solved with (2r-1.5)n+o(n) transport steps, i.e. in about 2.5n steps for r=2. The general h-h sorting problem, h⩾4r-4 can be solved within a number of transport steps that asymptotically differs by a factor of at most 3 from the trivial bisection bound. Furthermore, the bisection bound is asymptotically tight for sequences of h permutation routing problems, h=4cr, c⩾1, and for so-called offline routing