Tight Bounds on the Complexity of Parallel Sorting.

Abstract

In this paper, we prove tight upper and lower bounds on the number of processors, information transfer, wire area and time needed to sort N numbers in a bounded-degree fixed-connection network. Keywords include: Area-time tradeoffs; circuit complexity; communication complexity; fixed-connection network; information transfer; packet routing; parallel computation; sorting; universal computer; very large scale integration.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1985
Accession Number
ADA154726

Entities

People

  • T. Leighton

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Comparators
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Information Processing
  • Information Transfer
  • Large Scale Integration
  • Military Research
  • Parallel Computing
  • Parallel Processing
  • Permutations
  • Supercomputers
  • Technical Information Centers
  • Very Large Scale Integration

Fields of Study

  • Computer science

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.