Accession Number:

AD0759248

Title:

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

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1972-08-01

Pagination or Media Count:

14.0

Abstract:

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

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE