A logarithmic time sort for linear size networks


Journal Article

A randomized algorithm that sorts on an N node network with constant valence in O(log N) time is given. More particularly, the algorithm sorts N items on an N-node cube-connected cycles graph, and, for some constant k, for all large enough α, it terminates within kα log N time with probability at least 1 - N-α. © 1987, ACM. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Valiant, LG

Published Date

  • January 1, 1987

Published In

Volume / Issue

  • 34 / 1

Start / End Page

  • 60 - 76

Electronic International Standard Serial Number (EISSN)

  • 1557-735X

International Standard Serial Number (ISSN)

  • 0004-5411

Digital Object Identifier (DOI)

  • 10.1145/7531.7532

Citation Source

  • Scopus