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) : Reif,John H ; Valiant,Leslie G

PDF Url : ADA114857

Report Date : May 1982

Pagination or Media Count : 28

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 0(N) keys, the algorithm's 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)

Descriptors :   *Algorithms, *Network flows, Probability, Problem solving, Sorting, Routing, Sequential analysis, Computations

Subject Categories : Statistics and Probability
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE