Accession Number : AD0759248

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

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Habermann,Nico

Report Date : AUG 1972

Pagination or Media Count : 14

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)

Descriptors :   (*COMPUTER PROGRAMMING, ALGORITHMS), SET THEORY, PERMUTATIONS, THEOREMS

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE