A Sorting Network on Trees
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 Δ.
A. Banerjee and D. Richards, "A Sorting Network on Trees," Parallel Processing Letters, vol. 29, no. 4, World Scientific Publishing Co. Pte Ltd, Dec 2019.
The definitive version is available at https://doi.org/10.1142/S0129626419500154
Keywords and Phrases
Complexity; Oblivious Sorting; Sorting Network
International Standard Serial Number (ISSN)
Article - Journal
© 2019 World Scientific Publishing Co. Pte Ltd, All rights reserved.
01 Dec 2019