PARALLEL PERMUTATION AND SORTING ALGORITHMS.

David Nassimi, Sartaj Sahni

Research output: Contribution to conferencePaperpeer-review

Abstract

0(k log N) algorithms are obtained for permuting and sorting N data items on cube and perfect shuffle computers with N**1** plus **1**/**k processing elements, 1 less than equivalent to k less than equivalent to log N. These algorithms directly lead to a generalized-connection-network construction having 0(k log N) delay and 0(k N**1** plus **1**/**k log N) contact pairs. This network has the advantage that the switches can be set in 0(k log N) time by either a cube or perfect shuffle computer with N**1** plus **1**/**k processing elements.

Original languageEnglish (US)
Pages1-10
Number of pages10
StatePublished - Jan 1 1979
Externally publishedYes
EventProc Annu Allerton Conf Commun Control Comput 17th - Monticello, IL, USA
Duration: Oct 10 1979Oct 12 1979

Conference

ConferenceProc Annu Allerton Conf Commun Control Comput 17th
CityMonticello, IL, USA
Period10/10/7910/12/79

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'PARALLEL PERMUTATION AND SORTING ALGORITHMS.'. Together they form a unique fingerprint.

Cite this