On An Array Sorting Problem of Kosaraju.

Abstract

An array sorting problem is shown to have a linear lower time bound for n x n arrays. This negatively settles a conjecture of Kosaraju. Several other sorting schemes are considered, but all fail to improve performance. The impossibility of better than linear time sorting bounds for arrays with local rules is conjectured.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1977
Accession Number
ADA039874

Entities

People

  • Lawrence H Snyder
  • Raymond E. Miller
  • Richard J. Lipton

Organizations

  • Yale University

Tags

Communities of Interest

  • Counter IED

DTIC Thesaurus Topics

  • Computer Science
  • Computers
  • Connecticut
  • Continents
  • Contracts
  • Geographic Regions
  • Hypotheses
  • Information Systems
  • Iterations
  • Military Research
  • New York
  • North America
  • Transitions
  • Universities

Readers

  • Seismology
  • Team-Based Human-Centered Cognitive Task Decision Making and Information Performance.
  • Theoretical Analysis.