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 depth sorting network on a tree with maximum degree .
References
- 1. , The Art of Computer Programming, Vol. 3: Sorting and searching, 2nd edn. (1998). Google Scholar
- 2. , An 0(n log n) sorting network, in Proc. of the Fifteenth Annual ACM Symposium on Theory of Computing (ACM, 1983), pp. 1–9. Crossref, Google Scholar
- 3. , Sorting networks and their applications, in Proc. of the Spring Joint Computer Conference,
April 30–May 2, 1968 (ACM, 1968), pp. 307–314. Crossref, Google Scholar - 4. , Hypercubic sorting networks, SIAM Journal on Computing 27(1) (1998) 1–47. Crossref, ISI, Google Scholar
- 5. , A super-logarithmic lower bound for hypercubic sorting networks, in International Colloquium on Automata, Languages, and Programming (Springer, 1994), pp. 618–629. Crossref, Google Scholar
- 6. , An optimal sorting algorithm for mesh connected computers, in Proc. of the Eighteenth Annual ACM Symposium on Theory of Computing (ACM, 1986), pp. 255–263. Crossref, Google Scholar
- 7. , Routing permutations on graphs via matchings, SIAM Journal on Discrete Mathematics 7(3) (1994) 513–530. Crossref, ISI, Google Scholar
- 8. , Sorting networks on restricted topologies, in Int. Conf, on Current Trends in Theory and Practice of Informatics (Springer, 2019), pp. 54–66. Crossref, Google Scholar


