Parallel Neighbor-Sort (or the Glory of the Induction Principle),

Array A1N N or 2 is to be sorted in ascending order using procedure NSi which arranges the values of an adjacent pair Ai, Ai1 in the right order. It is shown that a parallel process P which can perform at least N divided by 2 executions of procedure NS in parallel will sort array A in p steps where p or N. The proof is based on the observation that the distance of the position of a number in array A after p steps and its final position is bounded by N - p. Author