Indexing functions and time lower bounds for sorting on a mesh-connected computer

Yijie Han, Yoshihide Igarashi, Miroslaw Truszczynski

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


We introduce a parameter of indexing functions and show its relation to lower bounds for sorting algorithms on mesh-connected computers that follow from the Chain Theorem. We give lower and upper bounds for the parameter. Conclusions from our results are: (1) no matter what indexing function is used any sorting algorithm must execute 2.27n + Θ(1) steps; (2) the best lower bound true for all indexing functions that we can hope to prove by the Chain Theorem argument is 2.5n + Θ(1).

Original languageEnglish
Pages (from-to)141-152
Number of pages12
JournalDiscrete Applied Mathematics
Issue number2
StatePublished - Apr 30 1992

Bibliographical note

Copyright 2014 Elsevier B.V., All rights reserved.


  • Sorting
  • complexity
  • indexing function
  • indexing scheme
  • lower bound
  • mesh-connected processor array
  • parallel computation

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Indexing functions and time lower bounds for sorting on a mesh-connected computer'. Together they form a unique fingerprint.

Cite this