Accession Number:

ADA114857

Title:

A Logarithmic Time Sort for Linear Size Networks.

Descriptive Note:

Technical rept.,

Corporate Author:

HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s):

Report Date:

1982-05-01

Pagination or Media Count:

28.0

Abstract:

We give a probabilistic algorithm for sorting on constant valence networks of N nodes such as the cube-connected cycles. We prove that for any input set of 0N keys, the algorithms execution time is greater than a constant times log N with vanishingly low likelihood. Since this constant factor is small our parallel sorting algorithm may be practical to implement. Author

Subject Categories:

  • Statistics and Probability
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE