Parallel Neighbor-Sort (or the Glory of the Induction Principle),
Abstract
Array A(1:N) (N > or = 2) is to be sorted in ascending order using procedure NS(i) which arranges the values of an adjacent pair A(i), A(i+1) 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1972
- Accession Number
- AD0759248
Entities
People
- Nico Habermann
Organizations
- Carnegie Mellon University