
Accession Number : AD0759248
Title : Parallel NeighborSort (or the Glory of the Induction Principle),
Corporate Author : CARNEGIEMELLON 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