A Sorting Network on Trees

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

International Standard Serial Number (ISSN)

0129-6264; 1793-642X

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

01 Dec 2019

Link to Full Text

Share

 
COinS