Skip to main content
Article
A Sorting Network on Trees
Parallel Processing Letters
  • Avah Banerjee, Missouri University of Science and Technology
  • Dana Richards
Abstract

Sorting networks are a class of parallel oblivious sorting algorithms. Not only do they have interesting theoretical properties but they can be fabricated. A sorting network is a sequence of parallel compare-exchange operations using comparators which are grouped into stages. This underlying graph defines the topology of the network. The majority of results on sorting networks concern the unrestricted case where the underlying graph is the complete graph. Prior results are also known for paths, hypercubes, and meshes. In this paper we introduce a sorting network whose underlying topology is a tree and formalize the concept of sorting networks on a restricted graph topology by introducing a new parameter for graphs called its sorting number. The main result of the paper is a description of an O(min(nΔ2,n2)) depth sorting network on a tree with maximum degree Δ.

Department(s)
Computer Science
Keywords and Phrases
  • Complexity,
  • Oblivious Sorting,
  • Sorting Network
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2019 World Scientific Publishing Co. Pte Ltd, All rights reserved.
Publication Date
12-1-2019
Publication Date
01 Dec 2019
Disciplines
Citation Information
Avah Banerjee and Dana Richards. "A Sorting Network on Trees" Parallel Processing Letters Vol. 29 Iss. 4 (2019) ISSN: 0129-6264; 1793-642X
Available at: http://works.bepress.com/avah-banerjee/2/