A Logarithmic Time Sort for Linear Size Networks.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1982
Accession Number
ADA114857

Entities

People

  • John Reif
  • Leslie G. Valiant

Organizations

  • Harvard University

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Binomials
  • Buildings And Structures
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Distributed Computing
  • Military Research
  • New York
  • Parallel Computing
  • Probability
  • Random Variables
  • Research Facilities
  • Sequences
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Parallel and Distributed Computing.
  • Regression Analysis.