arXiv:1612.06473v2 [cs.DS] 20 Jan 2017

Sorting Networks On Restricted Topologies
Indranil Banerjee

Dana Richards

Igor Shinkar

ibanerje@gmu.edu

richards@cs.gmu.edu

igors@berkeley.edu

George Mason University

George Mason University

UC Berkeley

January 23, 2017
Abstract
The sorting number of a graph with n vertices is the minimum depth of a sorting
network with n inputs and n outputs that uses only the edges of the graph to perform
comparisons. Many known results on sorting networks can be stated in terms of sorting
numbers of different classes of graphs. In this paper we show the following general
results about the sorting number of graphs.
1. Any n-vertex graph that contains a simple path of length d has a sorting network
of depth O(n log(n/d)).
2. Any n-vertex graph with maximal degree ∆ has a sorting network of depth O(∆n).
We also provide several results relating the sorting number of a graph with its routing number, size of its maximal matching, and other well known graph properties.
Additionally, we give some new bounds on the sorting number for some typical graphs.

1

Introduction

In this paper we study oblivious sorting algorithms. These are sorting algorithms whose
sequence of comparisons is made in advance, before seeing the input, such that for any
input of n numbers the value of the i’th output is smaller or equal to the value of the j’th
output for all i < j. That is, for any permutation of the input out of the n! possible, the
output of the algorithm must be sorted. A sorting network, which typically arises in the
context of parallel algorithms, is an oblivious algorithm where the comparisons are grouped
into stages, and in each stage the compared pairs are disjoint. In this paper we explore the
situation where a given graph specifies which keys are allowed to be compared. We regard a
sorting network as a sequence of stages, where each stage corresponds to a matching in the
graph and a comparator is assigned to each matched pair. There are fixed locations, each
containing a key, and a comparator looks at the keys at the endpoints of the edges of the
matching, and swap them if they are not in the order desired by the underlying oblivious
algorithm. Therefore, we say that the underlying algorithm induces a directed matching.
1

The locations are ordered, and the goal is to have the order of the keys match the order
of the locations after the execution of the algorithm. The depth of a sorting network is the
number of stages, and the size is the total number of edges in all the matchings. Note that
for an input of length n at most bn/2c comparisons can be performed in each step, and hence
the well-known lower bound of Ω(n log(n)) comparisons in the sequential setting implies a
Ω(log(n)) lower bound on the depth on the network, that is, the number of stages in the
network.
A large variety of sorting network have been studied in the literature. In their seminal
paper, Ajtai, Komlós, and Szemerédi [1] presented a construction of a sorting network of
depth O(log n). We will refer to it as the AKS sorting network. In this work we explore
the question of constructing a sorting network where we are given a graph specifying which
keys are allowed to be compared. We define the sorting number of a graph G, denoted by
st(G), to be the minimal depth of a sorting network that uses only the edges of G. The
AKS sorting network can be interpreted as a sorting network on the complete graph, i.e.,
st(Kn ) = O(log(n)). More precisely, the AKS construction specifies some graph GAKS whose
maximal degree is O(log(n)) and st(GAKS ) = O(log(n)).
The setting where the comparisons are restricted to the n-vertex path graph, denoted
by Pn , is perhaps the easiest case. It is well known that st(Pn ) = n, which follows from
the fact that the odd-even transposition sort takes n matching steps (see, e.g., [7]). For the
hypercube graph Qd on n = 2d vertices we can use the Batcher’s √bitonic sorting network,
which has a depth of O((log n)2 ) [5]. This was later improved to 2O( log log n) log n by Plaxton
n log log n
) due to Leighton and Plaxton [11].
and Suel [10]. We also have a lower bound of Ω( log
log log log n
For the square mesh Pn × Pn it is known that st(Pn × Pn ) = 3n + o(n), which is tight with
respect to the constant factor of the largest term. This follows from results of Schnorr and
Shamir [12], where they introduced the 3n-sorter for the square mesh. We also have a tight
result for the general d-dimensional mesh of Θ(dn) due to Kunde [8]. These results are, in
fact, more general, as they apply to meshes with non-uniform aspect ratios.
Graph
Complete Graph (Kn )
Hypercube (Qn )
Path (Pn )
Mesh (Pn × Pn )
d-dimensional Mesh
Tree
d-regular Expander

Lower Bound
log n
log n log log n
Ω( log log log n )
n−1
√
3n − 2 n − 3
Ω(dn)

Complete p-partite
Graph (Kn/p,...,n/p )
Pyramid (d, N )

Ω(log n)

Ω(log n)

Upper Bound
Remark
O(log n)
AKS Network [1]
√
O( log log n)
2
log n
Plaxton et. al[10, 11]
n
Odd-Even Trans. [7]
3/4
3n + O(n )
Schnorr & Shamir [12]
O(dn)
Kunde [8]
O(min(∆n, n log (n/d)))
This paper
O(d log3 (n))
This paper
O(log n)

This paper

O(dN 1/d )

This paper

Table 1: Known Bounds On The Sorting Numbers Of Various Graphs

2

2

Definitions

Formally, we study the following restricted variant of sorting networks. We begin by taking
a graph G = (V, E), where the vertices correspond to the locations of an oblivious sorting
algorithm, V = {1, 2, . . . , |V |}. The keys will be modeled by weighted pebbles, one per
vertex. Let a sorted order of G be given by a permutation π that assigns the rank π(i)
to the vertex i ∈ V . The edges of G represent pairs of vertices where the pebbles can be
compared and/or swapped. Given a graph G the goal is to design a sorting network that
uses only the edges of G. We formally define such a sorting network.
Definition 2.1 (Sorting Network on a Graph). A sorting network is a triple S(G, M, π)
such that:
1. G = (V, E) is a connected graph with a bijection π : V → {1, . . . , |V |} specifying the
sorted order on the vertices. Initially, each vertex of G contains a pebble having some
value.
2. M = (Mi , . . . , Mt ) is a sequence of matchings in G, for which some edges in the
matching are assigned a direction. Sorting occurs in stages. At stage i we use the
matching Mi ∈ M to exchange the pebbles between matched vertices according to their
→ when swapped the smaller of the two pebbles goes to u. If
orientation. For an edge −
uv,
an edge is undirected then the pebbles swap regardless of their order.
3. After |M| stages the vertex labeled i contains the pebble whose rank is π(i) in the sorted
order. We stress that this must hold for all (n!) initial arrangement of the pebbles. |M|
is called the depth of the network.
Definition 2.2 (Sorting Number). Let G be a graph, and let π be a sorted order of G. Define
st(G, π) to be the minimum depth of a sorting network S(G, M, π). The sorting number of
G, denoted by st(G), is defined as the minimum depth of any sorting network on G, i.e.,
st(G) = minπ st(G, π).

3

Our Results

The AKS sorting network can be trivially converted into a network of depth O(n log(n)) by
making a single comparison in each round. However, it is not clear a-priori whether for any
graph there is a network of depth O(n log(n)). We show that this bound indeed holds for all
graphs.
Theorem 3.1. Let G be an n-vertex graph, and suppose that G contains a simple path of
length d. Then st(G) = O(n log (n/d)). In particular, for every n-vertex graph G it holds
that st(G) = O(n log(n)).
This bound is tight for the star graph K1,n−1 as at most 1 comparison can be made per
round, and hence st(K1,n−1 ) = Θ(n log(n)).
If the maximal degree of G is small, it possible to show a better upper bound on st(G).
3

Theorem 3.2. Let G be an n-vertex graph with maximal degree ∆. Then st(G) = O(∆n).
Next, we relate the sorting number of a graph to it routing number, and the size of its
maximal matching.
Theorem 3.3. Let G be an n-vertex graph with routing number rt(G) and matching of size
ν(G). Then st(G) = O(n log(n) · rt(G)
).
ν(G)
Next, we upper bound st(G) for graphs G that contain a large subgraph H whose st(H)
is small.
Theorem 3.4. Let G be an n-vertex graph, and let H be a vertex-induced subgraph of G on
p vertices. Then


n
n
log( ) · (rt(G) + st(H)) .
st(G) = O
p
p
Theorems 3.1-3.4 above will be proven in Section 5.
In Section 6 we prove bounds on some concrete families of graphs, including the complete
p-partite graph, expander graphs, vertex transitive graphs, Cayley graphs, and the pyramid
graph.

4

Routing via Matchings

In order to prove some of the results in this paper we need to define the model of routing
via matchings, originally introduced by Alon et. al [2]. Given a connected labeled graph
G = (V, E), where each vertex i ∈ V is initially occupied by a labeled pebble that has
a unique destination π(i), the routing time rt(G, π) is defined as the minimum number of
matchings required to move each pebble from i to its destination vertex labeled π(i), where
pebbles are swapped along matched edges. The routing number of G denoted by rt(G) is
defined as the maximum of rt(G, π) over all such permutations π : V → V . We start with
the following simple lemma.
Lemma 4.1. For any graph G and any order π of the vertices of G it holds that
max{rt(G), log |G|} ≤ st(G, π) ≤ st(G) + rt(G).
Proof. We show first that rt(G, σ) ≤ st(G, π) for any two permutations π, σ of the vertices.
Indeed, suppose that the keys of the pebbles are {1, . . . , |V |}. For all i ∈ V place the pebble
ranked i in the vertex σ −1 (π −1 (i)). Then, there exists a sorting network of depth st(G, π)
that sends the pebble ranked i to π −1 (i) for all i ∈ V . That is, the pebble from the vertex
j = σ −1 (π −1 (i)) is sent to the vertex π −1 (i) = σ(j). Therefore, rt(G, σ) ≤ st(G, π) for all
permutations σ, and thus rt(G) ≤ st(G, π). Second part of the lower bound follows from
the standard information theoretic argument for oblivious sorting algorithms. We know that
any sorting network must make Ω(|G| log |G|) compare-exchanges and the size of the largest
matching is at most |G|/2, and hence st(G, π) ≥ Ω(log(|G|)).
4

For the upper bound let S(G, M, τ ) be a sorting network on G of depth st(G) = st(G, τ ).
We use τ to create another sorting network S(H, M, π) of depth at most st(G) + rt(G). This
is done in two stages. First we apply the sorting network S(H, M, τ ). After this stage we
know that the pebble at vertex i has a rank τ (i). Next, we apply a routing strategy with
rt(G) steps that routes to the permutation π −1 ◦ τ , i.e., sending a pebble in the vertex i to
π −1 (τ (i)) for all i ∈ V . After this step the vertex i contains the pebble of rank π(i). This
proves that st(G, π) ≤ st(G) + rt(G).
The above lemma implies that if we construct a sorting network for an arbitrary sorted
order on the vertices then we suffer a penalty of rt(G) on the depth of our network as
compared to the optimal one.

4.1

Routing on subgraphs of G

Below, we study the notion of routing a subset of the pebbles to a specific subgraph. We
start with the following lemma.
Lemma 4.2. Let T be a tree with diameter d, and let P be a path of length d in T . Then,
we can route any set of d pebbles to P in 3d steps.
Proof. Denoting the number of the pebbles by k, we prove that we can route any set of k
pebbles to any subset Pk ⊆ P of size |Pk | = k, in at most d + 2(k − 1) steps. The proof is
by induction on k The case k = 1 is trivial, since d is the diameter of T .
For the induction step let k ≥ 2, let v1 , . . . , vk be the locations of the k pebbles, and
let Pk be a subset of P of size k. Suppose without loss of generality that dist(vk , Pk ) ≥
dist(vi , Pk ) for all i < k. Note that we may assume that dist(vk , Pk ) > 0, as otherwise all
pebbles are already in Pk . Let u∗ ∈ Pk be a vertex in Pk , that is the closest to vk , and let
(vk = s0 , s1 , . . . , sr = u∗ ) be the shortest path from vk to u∗ , where r = dist(vk , P ) ≤ d.
By the inductive hypothesis there is a sequence of d + 2(k − 2) matchings routing the
pebbles v1 , . . . , vk−1 to Pk \{u∗ }. We would like to argue now that it is possible to route vk to
u∗ using the two extra steps by letting v “follow” the other pebbles so as not to interrupt with
their routing from the induction hypothesis. This is indeed possible, as we show below. Note
that by applying the sequence of d + 2(k − 2) matchings from the induction hypothesis, after
d+2(k −2) rounds none of the vertices v1 , . . . , vk−1 is any of the vertices {sr−2 , sr−1 , sr = u∗ }.
This is because (vk = s0 , s1 , . . . , sr = u∗ ) is the shortest path from vk to Pk , and in particular
sr−2 , sr−1 ∈
/ Pk . By the assumption that dist(vk , Pk ) ≥ dist(vi , Pk ), it follows that after the
d + 2(k − 2) − 1 rounds (i.e., one round before the last one) none of the vertices in v1 , . . . , vk−1
is in {sr−3 , sr−2 }. This is because dist(sr−2 , Pk ) = 2 and dist(sr−3 , Pk ) = 3, and so in the
last step a vertex from {sr−3 , sr−2 } could not reach Pk . Analogously, for all j ≤ r after the
(d + 2(k − 2) − j) rounds none of the vertices in v1 , . . . , vk−1 is in {sr−j−2 , sr−j−1 }. Therefore,
(recall that r ≤ d) we may take the routing sequence from the inductive hypothesis, and
augment its last r − 2 steps by moving the pebble from vk to u∗ along the shortest path
(vk = s0 , s1 , . . . , sr−2 ), and then in the last 2 rounds the matchings will be just singletons
moving this pebble from sr−2 to u∗ .
5

Motivated by the lemma above, we discuss below the question of partial routing, where
only a small number of pebbles are required to reach their destination.
Definition 4.3. Given a graph G = (V, E) let A, B ⊂ V be two subset of vertices with
|A| = |B|, not necessarily distinct. Let πAB be a bijection between A and B. Routing of
the pebbles from A to their respective destinations on B given by πAB is defined as a partial
routing in G, where each pebble in a ∈ A in required to reach πAB (a) ∈ B using the edges of
G (and there are no requirements on the pebbles outside A).
1. Define rt(G, A, B, πAB ) be the minimum number of matchings needed to route every
pebble a ∈ A to πAB (a) ∈ B using the edges of G.
2. Define rt(G, A, B) = maxπAB rt(G, A, B, πAB ).
3. For U ⊆ V define rtU (G) = maxA⊆V rt(G, A, U ).
4. For p ∈ 1, . . . , |V | define rtp (G) = maxA,B⊂V,|A|=|B|≤p rt(G, A, B).
Clearly, for any n-vertex graph G we have rt(G) = rtn (G). Some of the bounds for rt(G)
also holds for rtp (G). For example, rtp (G) ≥ d, where d is the diameter of G. Furthermore,
rtp (G) = Θ(rt(G)) for any p if and only if rt(G) = Θ(d). We illustrate rtp (G) by computing it
explicitly for some typical graphs. Recall that rt(Kn ) = 2. It is easy to see that rtp (Kn ) = 2
for all p ≥ 3, and rt2 (Kn ) = 1. For the complete bipartite graph we have rtn/2 (Kn/2,n/2 ) = 2
and is rtp (Kn/2,n/2 ) = 4 for p > n/2.
Theorem 4.4. For any tree T with diameter d, rtp (G) = O((d + p) min(d, log nd )).
Proof. The proof is similar to the proof used in [2] for determining the routing number of
trees. We find a vertex r whose removal disconnects the tree into a forest of trees each of
which is of size at most n/2. Let (T1 , . . . , Tr ) be the set of trees in the forest, with r ∈ T1 .
For a tree Ti let Si be the set of “improper” pebbles that need to be moved out of Ti . All
other pebbles in Ti are “proper”. In the first round we move all the pebbles in Si as close to
the root of Ti as possible, for all i. Using the argument used in [2] it can be shown that for
a tree with diameter d this first phase can be accomplished in 2d steps for some constant c1 .
First we label each node in Ti as odd or even based on their distance from ri , the root of Ti .
In each odd round we match nodes in odd layers with proper pebbles to one of its children
containing an improper pebble if one exists. Similarly, in even rounds we match nodes in
even layers with proper pebbles to one of its children containing an improper pebble if one
exists. Since T has diameter d any path from ri to some leaf must be of length at most
d − 1. Now consider an improper pebble u initially at distance k from the root. During a
pair of odd-even matchings either the pebble moves one step closer to the root or one of the
following must be true: (1) another pebble from one of its sibling node jumps in front of it or
(2) there is some improper pebble already in front of it. It can then be argued (we omit the
details here) that after c1 d matchings for some constant c1 if u ends up in position j from
ri then all pebbles between u and ri must be improper. Next we exchange a pair of pebbles
6

between subtrees using the root vertex r, since at most p/2 pairs needs to be exchanged, the
arguments used in [2] can be modified to show that this phase also takes c2 p steps for some
constant c2 . After each pebble is moved to their corresponding destination subtrees we can
route them in parallel. Noting that each tree Ti has diameter at most d − 1. Hence we have
the following recurrence:
T (n, d, p) ≤ T (n/2, d − 1, p) + c1 d + c2 p

(1)

where T (n, d, p) is the time it takes to route p pebbles in a tree of diameter d with n vertices.
Taking T (·, d, p) = O(d), and solving (1) gives the stated bound of the lemma.

5

General Upper Bounds on st(G)

Below we prove Theorem 3.1 stating that if G contains a simple path of length d, then
st(G) = O(n log (n/d)).
Proof of Theorem 3.1. It is easy to see that if G contains a simple path of length d, then
G has a spanning tree T such that with diameter at least d. The proof follows easily from
Theorem 3.4 and Lemma 4.2. Indeed, in the setting of Theorem 3.4, let H be a path of
length d in T . Then st(H) = d. By Theorem 3.4 if any set of d vertices can be routed to H
in r steps, then st(T ) ≤ O( nd log( nd ) · (r + st(H))). By Lemma 4.2 we have r = O(d), and
thus st(G) ≤ st(T ) = O(n log(n/d)).
Next, we prove Theorem 3.2. The proof is essentially from [3], who proved that the
acquaintance time of a G, defined in [6], is upper bounded by 20∆n. The basic idea is to use
an n round sorting network for Pn , and simulate this network in T with an overhead that
depends only on ∆.
Proof of Theorem 3.2. Clearly it is sufficient to prove that for a spanning subgraph T of G
it holds that st(T ) ≤ 20∆n. A contour of a tree T is a closed walk on 2n − 1 vertices that
crosses each edge exactly twice, and visits each vertex v exactly deg(v) times. Such a contour
can be constructed by considering a depth-first search walk on T .
Let Γ be a contour of T . Consider Γ as a path on 2n − 1 vertices, and let π denote the
projection from Γ to T . We claim that for each x ∈ T it is possible to choose a vertex of Γ
from π −1 (x) so that the gaps between the consecutive chosen vertices along Γ are at most
3. To do this, let r be an arbitrarily chosen first vertex of Γ. Recall that T is assumed to
be a tree. For each vertex x ∈ T whose distance from r is even we pick the first vertex of
Γ projecting to x, and for each vertex x ∈ T whose distance from r is odd we pick the last
one. Note that Γ visits each leaf of the tree exactly once. Between consecutive visits to the
leaves the contour descends towards the root, and then ascends to the next leaf. Along the
descent, the vertices are visited for the last time, and so every other vertex is selected. Along
the ascent, the vertices are visited for the first time, and also every other vertex is selected.
Hence, we have at most three steps of Γ between any two consecutive selected vertices.

7

Consider the odd-even transposition sort in Pn , the n-vertex path whose vertices are
denoted by {1, 2, . . . , n}. In the odd rounds we compare the pebbles on the edges {(i, i + 1) :
i odd}. In the even rounds we compare the pebbles on the edges {(i, i + 1) : i even}. It is
known that after n rounds the pebbles in Pn are sorted [7].
In order to present a sorting network in T with at most 20∆ · n rounds we emulate the
foregoing sorting network in Pn by simulating each round of the transposition sort with a
sequence of at most 20∆ rounds in T .
First, consider the path Γ with 2n − 1 vertices, and place n pebbles on Γ in the selected
vertices of Γ, so that the distance between any two consecutive pebbles is at most 3. Our goal
is to sort the n pebbles on Γ, which, in particular, implies sorting in T . Since the pebbles are
not located in consecutive vertices of the path, every round of the odd-even transposition
sort for Pn will require several (at most 5) rounds of sorting in Γ. We then show how to
emulate these moves by a sorting network in T with the sorted order defined by the linear
order of the marked vertices of Γ.
Let i < j be two consecutive marked vertices of Γ, and let pi and pj be the pebbles in
the corresponding vertices. In order to compare the pebbles pi and pj we can perform a
sequence of swaps (without comparisons) in Γ along the edges (i, i + 1), . . . , (j − 2, j − 1),
which brings the pebble pi to the vertex j − 1, followed a comparison step (j − 1, j), which
places the pebble max(pi , pj ) into the vertex j, and finally, performing the sequence of swaps
(j−1, j−2), . . . , (i+1, i) (again, without comparisons) in order to bring the pebble min(pi , pj )
to the vertex i. The gaps between consecutive pebbles are at most 3, and hence it takes at
most 5 steps on Γ to perform such a swap. These swaps projected on T result in comparison
of the pebbles in the vertices π(i) and π(j), leaving all other pebbles in their place.
The difficulty is that in the graph T the steps for swapping a pair of pebbles pi and pj
could interfere with the steps for swapping another pair pi0 and pj 0 . This happens if the
projections to T of the intervals [i, j] and [i0 , j 0 ] in the path Γ intersect. If there are no such
intersections, then all the swaps for all pairs could be carried out in parallel and we would
have a sorting network in T with 5n rounds.
In order to solve this problem, we separate each round of odd-even transposition sort in Pn
into several sub-rounds, so that conflicting pairs of intervals are in different sub-rounds, and
then split each sub-round into at most 5 steps in Γ as described above. By the assumption
on the maximal degree on T , the path Γ visits each vertex of T at most ∆ times. Thus, since
the intervals [i, j] of Γ that we care about in each round are vertex disjoint in Γ, each vertex
of T is contained in at most ∆ such intervals. Each interval consists of at most 4 vertices of
T , and therefore each interval [i, j] is in conflict (i.e., their projections to T intersect) with
at most 4(∆ − 1) other intervals [i0 , j 0 ] participating in the current round.
It is well known that if a graph has maximum degree D, then its chromatic number is at
most D + 1. Applying this to the conflict graph of the intervals to be swapped in one round
of the odd-even transposition sort we see that we can assign each interval [i, j] of Γ one of
4∆ − 3 colors, so that conflicting intervals have different colors.
We now split each round of the transposition sort on Γ into 4∆ − 3 sub-rounds, where in
every sub-rounds we swap all pairs of the same color that are to be swapped in this round of

8

the transposition sort in Pn . Finally, we simulate this strategy in Pn by replacing each subround with at most 5 steps in Γ as described above. Our coloring of the intervals guarantees
that there are no conflicting intervals, and hence the comparisons can be carried out in T
in parallel. Therefore, each round of the odd-even transposition sort can be simulated by
5(4∆ − 3) rounds in T , and hence st(T, π) ≤ 5(4∆ − 3)n, where π is the order defined by
the natural linear order in Γ. This completes the proof of the theorem.
Next, we prove Theorem 3.3 stating that st(G) = O(n log(n) · rt(G)
), where rt(G) is the
ν(G)
routing number of G, and ν(G) is the size of the maximal matching in G.
Proof of Theorem 3.3. We prove the theorem by using G to simulate the AKS sorting network on the complete graph Kn of depth O(log(n)). Specifically, we show that each stage
n
rt(G)) stages
(a matching) of the sorting network on Kn can be simulated by at most O( ν(G)
(matchings) in G. Let M be a matching at some stage of the AKS sorting network on
the complete graph. We simulate the compare-exchanges and swaps in M by a sequence of
matchings in G as follows. First we partition the edges in M into t = dn/ν(G)e disjoint subsets M = M1 ∪ · · · ∪ Mt , where |Mi | = ν(G) for all except maybe the last set Mt , which can
be smaller. Let MG be a maximal matching in G. Corresponding to each pair (u, v) ∈ Mi
we pick a distinct pair (u0 , v 0 ) ∈ MG , this can always be done since the sets Mi and MG
are of the same size. Note that the pair (u, v) may not be adjacent in G, and so, we route
each pair (u, v) ∈ Mi to its destination in (u0 , v 0 ) ∈ MG . This can be done in rt(G) steps,
where each step consists of only undirected matchings. Once the pairs have been placed in to
their corresponding positions we relabel the vertices such that the pair labeled (u0 , v 0 ) is now
(u, v). Unmatched vertices keep their label. Since the pairs in Mi are now adjacent in G we
can perform the compare-exchange or swap operation according to Mi . Therefore, the total
number of matchings to execute the ith set of compare-exchanges and swaps in Mi is rt(G)+1
in G. We remark that the routing maintains the oblivious nature of the network, and the
swaps are made while routing, which are data independent. We perform all the operations in
each Mi successively, while keeping track of the relabeling of the vertices that occur at each
n
·rt(G))
sub-stage. This implies that we can simulate M using at most (rt(G)+1)·t = O( ν(G)
matchings in G. Therefore, since the depth of the AKS sorting network on the complete
graph Kn is O(log(n)), we conclude that st(G) = O(n log(n) · rt(G)
), as required.
ν(G)
Next we prove Theorem
 3.4, saying that if H be
 a vertex-induced subgraph of G on p
n
n
vertices then st(G) = O p log( p ) · (rt(G) + st(H)) .
Proof of Theorem 3.4 . Let us partition the vertex set V of G into q = dn/bp/2ce parts
V = A1 ∪ · · · ∪ Aq in a balanced manner (i.e., the size of each Ai is either bp/2c or bp/2c − 1).
Let Kq be a complete graph whose vertices are identified with {A1 , . . . , Aq }, and let S be an
oblivious sorting algorithm with O(q log q) comparisons on the complete graph Kq . (Here
the sequence of comparisons is performed sequentially, and not in parallel.) In an ordinary
sorting network in each step we perform a compare-exchange or a swap between two matched
vertices (i, j) so that if i < j, then the pebble in the vertex i will be smaller than the pebble
in j We will simulate S on G using a sorting network on H by sorting in each stage the
9

elements in Ai ∪ Aj . That is, for i < j we are going to sort the elements in Ai ∪ Aj so that
all the elements of Ai are smaller than every element of Aj , and the elements within each
subset are internally sorted. This is done using an optimal sorting network in H, which we
will denote by SH .
The key observation is that we can simulate any such compare-exchange in G between
pairs of sets in A in O(rt(G) + st(H)) steps. Indeed, suppose the k th round in S compares
the vertices i < j. In order to simulate this comparison we first route all the pebbles in
Ai ∪ Aj to the subgraph H and relabel the vertices. This relabeling is done so that we can
keep track of the vertices when sorting H. Then, we use SH to sort Ai ∪ Aj which takes
st(H) steps. Note that if |Ai ∪ Aj | < p we can still use the network SH to sort it by slightly
modifying the original network. Once the sorting is done we split up the sets again and
appropriately relabel the vertices so that the first |Ai | vertices in the sorted order on H will
now belong to Ai and the next |Aj | vertices will belong to Aj . If instead the k th comparison
is actually a swap then we simply swap the labels of the multisets (Ai is labeled Aj and vice
versa). Hence performing the above simulation takes O(rt(G) + st(H)) steps per compare
exchange or swap operation, which gives the result of the theorem.
In the proof of Theorem 3.4 above we only used an oblivious sorting algorithm with
O(q log q) comparisons on the complete graph Kq , and did not use the fact that the comparisons can be done in parallel, e.g., using the AKS sorting network. This is because
Theorem 3.4 only assumes that there is one subgraph H with small st(H). If instead we assumed that there are many such subgraphs, then we could sort the Ai ’s in different subgraphs
in parallel. This is described in the corollary below.
Corollary 5.1. Let G = (V, E) be an n-vertex graph. Let V = V1 ∪ . . . Vq be a partition
of the vertices, with |Vi | = n/q for all i ∈ {1, . . . , q}, and let Hi be the connected subgraph
induced by Vi for each i ∈ {1, . . . , q}. Then


st(G) = O log(q) · (rt(G) + max {st(Hk )}) .
k∈{1,...,q}

Proof sketch. The proof uses the same idea that Theorem 3.4. We start by partitioning the
vertex set V of G into 2q parts V = A1 ∪ · · · ∪ A2q of equal sizes. Then, we simulate oblivious
sorting algorithm on K2q with the sets Ai . The only difference is that instead of an oblivious
sorting algorithm with O(q log(q)) comparisons on the complete graph K2q we use the AKS
sorting network on 2q vertices of depth O(log(q)). In each round of the sorting network there
are at most q comparisons, and the corresponding sorting of Ai ∪ Aj can be performed in
parallel, one in each Hk in time st(Hk ).

6

Bounds on Concrete Graph Families

Below we state several results concerning the sorting time of some concrete families of graphs.
Proposition 6.1 (Complete p-partite graph). Let G be the complete p-partite graph Kn/p,...,n/p
on n vertices. Then st(G) = Θ(log n).
10

Proof. The lower bound is trivial. For the upper bound note that Kn/p,...,n/p contains the
bipartite graph Kb p2 c np ,d p2 e np . In particular, it contains a matching of size ν(G) = b p2 c · n/p
since Kn/p,...,n/p . Therefore, by Theorem 3 in [2] and the remark after the proof, we have
dpe

rt(G) ≤ rt(Kb p2 c np ,d p2 e np ) ≤ 2d b p2 c e + 2 ≤ 6, and hence by Theorem 3.3 it follows that st(G) ≤
2
O(log(n)).
Recall that a graph G is said to be a (n, d, λ)-expander if it is a d-regular graph on n
vertices and the absolute value of every eigenvalue of its adjacency matrix other than the
trivial one is at most λ.
3

3
d
Proposition 6.2 (Expander graphs). Let G be an (n, d, λ)-expander. Then st(G) ≤ O( (d−λ)
2 log (n)).
In particular, if λ < (1 − logc1(n) )d, then st(G) ≤ O(d · log2c+3 (n)).
 2

2
d
Proof. Recall from [2] that if G is an (n, d, λ)-expander, then rt(G) = O (d−λ)2 log (n) .
Therefore, since any d-regular graph contains a matching of size n/2d it follows from Theo3
d3
rem 3.3 that st(G) ≤ O( (d−λ)
2 log (n)).

Proposition 6.3 (Vertex transitive graphs). Let G be a verter transitive graph with n
vertices of degree polylog(n). Then diam(G) = O(polylog(n)) if and only if st(G) =
O(polylog(n)).
Proof. It is trivial that diam(G) ≤ st(G). For the other direcion, Babai and Szegedy [4]
showed that for vertex-transitive graphs if the diameter of G is O(polylog(n)) then its vertex
expansion is Ω(1/polylog(n)). Therefore, λ ≤ d(1 − 1/polylog(n)), where d = O(polylog(n))
is the degree of the graph. Therefore, by Proposition 6.2 we have st(G) = O(polylog(n)).
Next we bound the sorting number of cartesian product of two given graphs. Recall that
for two graphs G1 (V1 , E1 ) and G2 (V2 , E2 ) their Cartesian product is G1 G1 is the graph
whose set of vertices is V1 × V2 and ((u1 , u2 ), (v1 , v2 )) is an edge in G1 G1 if either u1 = v1 ,
(u2 , v2 ) ∈ E2 or (u1 , v1 ) ∈ E1 , u2 = v2 . Our next result bounds the sorting number of a
product graph in terms of sorting numbers of its components.
Corollary 6.4. Let G1 = (V1 , E1 ) and G2 = (V2 , E2 ) be two graphs and G = G1 G2 . Then
st(G) ≤ O(min(log |V1 |(rt(G) + st(G2 )), log |V2 |(rt(G) + st(G1 ))).
Proof. We will prove the corollary in terms of rt(G), and then use Theorem 4 in [2] saying
that rt(G) ≤ min{rt(G1 ), rt(G2 )} + rt(G1 ) + rt(G2 ). Since G has |V1 | vertex disjoint subgraphs that are copies of G2 we can apply Corollary 5.1 with these q = |V1 | subgraphs, and
all Hi being isomorphic to G2 . Therefore, we get
st(G) ≤ O(log(|V1 |) · (rt(G) + st(G2 ))
The bound st(G) ≤ O(log(|V2 |)·(rt(G)+st(G1 )) follows using the same argument by changing
the roles of G1 and G2 .
11

b1

b2

b3

b4

b5

G2
a1

A1

a2

A2
G1

a3

A3

a4

A2
G = G1 G2

Figure 1: The product graph G = G1 G2 . The rows highlighted by blue regions represents
copies G2 .
As an example of an application of the above corollary consider the d-dimensional mesh
Mn,d with nd vertices. We know that rt(Mn,d ) ≤ 2dn since Mn,d = Mn,d−1 × Pn . Therefore,
st(Mn,d ) ≤ O(log(nd−1 ) · (rt(Mn,d ) + st(Pn ))) = O(dn log(n)). Although this bound is not
optimal (it is known that st(Mn,d ) = O(dn)), we still find this example interesting.

6.1

The Pyramid Graph

A 1-dimensional pyramid with m-levels is defined as the complete binary tree of 2m −1 nodes,
where the nodes in each level are connected by a path (i.e., a one-dimensional mesh). We
treat the apex (root) to be at level 0, and subsequent levels are numbered in ascending order.
A 2-dimensional pyramid is shown in Figure 2. In this case each level l is a 2l × 2l square
mesh. Similarly a d-dimensional pyramid having m levels is denoted by 4m,d , where the level
l is a d-dimensional regular mesh of length 2l in each dimension. Clearly,Pthe size of layer l
2md −1
ld
is |Ml | = 2ld and the number of vertices in the graph is N = |4m,d | = m−1
l=0 2 = 2d −1 .
We treat a vertex x ∈ Ml as a vector in [1, 2l ]d which denotes its position on the mesh.
M0

M1

M2

Figure 2: A pyramid 43,2 in 3-dimension
12

In this section we prove an upper bound on st(4m,d ). In order to derive this bound we
make use of the following bound on the routing number of pyramid.
Lemma 6.5. Let 4m,d be the d-dimensional pyramid graph with m-levels. Then rt(4m,d ) =
O(dN 1/d ).

v00

M0

v10
M1

M2
v212
213

v215

Figure 3: The graph 403,2 after stripping way edges from 43,2
Proof. Given the pyramid 43,2 consider a subgraph 403,2 as shown in Figure 3. In literature
this graph is sometimes refer to as a multi-grid, see for example [9]. As we move down from
the apex we remove all but the “first” edge from the set of edges that connects a vertex to
its neighbors in the level below. The remaining edges that connects two adjacent layers will
be referred to as vertical edges. These edges can be grouped into disjoint vertical paths as
shown by the blue lines in Figure 3. The above construction naturally generalizes in higher
dimensions. Clearly rt(4m,d ) ≤ rt(40m,d ) where 40m,d is the multi-grid obtained from 4m,d .
We shall show rt(40m,d ) = O(dN 1/d ).
Let π be some input permutation. Without loss of generality we assume that π consists
only of 2-cycles or 1-cycles. From [2] we know that any arbitrary permutation can be written
as a composition of at most two such permutations. In order to route π we first route the
pebbles into their appropriate levels and then route within these levels. Routing consists of
five rounds where in the odd numbered rounds we route within the levels and in the even
numbered rounds we use the vertical paths to route between the levels. The first four rounds
are used to move the pebbles to their appropriate destination level.
Let vij be the j th node at level i, where j ∈ [0, ni − 1]. Let φk be the number of maximal
vertical paths of length k. For example, in Figure 3 we have φ2 = 1 and φ1 = 3. In general
in a 40m,d , φk = nm−k−1 − nm−k−2 for k ∈ [1, m − 2] and φm−1 = 1. We group the cycles in
π based on their source and destination level (in case of 1-cycles the source and destination
levels are the same). Let Pij (i < j) be the set of pebble pairs that need to be moved from
level i down to level j and
S vice-versa and Pii be the set of pebbles that stay in level i. Let
µij = |Pij |. Let Pi = i<j Pij be the set of pebble pairs that move a pebble up to level
i. We shall only use disjoint vertical paths of length m − i − 1 to route the pebbles in Pi .
13

During either even round each path of length m − i − 1 will be used, for some j, to swap two
pebbles between levels i and j; all other pebbles on that path will not move. As an example
consider the case in Figure 3. Suppose π(v00 ) = v21 . Then during the intra-level routing
on the first round we will move the pebble at v21 to v20 . All intermediate nodes on this
path, which in this case is just v10 will be ignored (i.e., a pebble on these nodes will return
to their original position at the end of the round). The four pebbles {v10 , v11 , v12 , v13 } will
only use
P the three paths of length 1 to move to the bottom level (if necessary). In general
|Pi | = j>i µij ≤ ni ≤ 2(ni −ni−1 ) = 2φm−i−1 . Hence we need at most two rounds of routing
along these vertical paths to move all pebbles in Pi .
Routing within the levels (which happens in parallel) is dominated by the routing number
1/d
of the last level which is known to be O(dnm ) = O(dN 1/d ) (for example, we can use Corollary
2 of Theorem 4 in [2]). Hence the three odd rounds take O(dN 1/d ) in total. In the even
rounds routing happens in parallel along the disjoint vertical paths. The routing time in this
case is O(m). Since, N 1/d = Ω(2m ), the even rounds do not contribute to the overall routing
time, which remains O(dN 1/d ), as claimed by the theorem.
Using the above theorem we give an upper bound on the sorting number of the pyramid.
Theorem 6.6 (pyramid). The sorting number for a pyramid 4m,d is O(d N 1/d ).
Proof. Let 4i,d denote the sub-pyramid from level 0 to i and let Mi be the d-dimensional
mesh at level i. Let πi be the sorted order on the mesh Mi . Note that πi : [1, 2i ]d → [ni ] is a
bijection and π0 is the identity permutation of order 1. Next we define a sorted order π for
the pyramid 4m,d based on the πi ’s. In π we assume the layers are sorted among themselves
in ascending order starting from the apex. So the vertex labeled (with respect to Mi ) i on
1/d
layer j has a global rank π(i) = πj (i) + |4j−1,d |. Recall that st(Mi ) = O(dni ) which is due
to Kunde[8] where he used the general snake-like ordering. From Lemma 4.1 we see that
this bound still holds if we replace the snake-like ordering with some arbitrary permutation.
Obviously in this case rt(Mi ) = Θ(st(Mi )). Next we describe the matchings M of sorting
the network S(4m,d , M, π) in terms of an oblivious sorting algorithm described below.
S(4m,d , M, π)
1. Route all pebbles of 4m−1,d to Mm−1 and sort them using the mesh.
2. Route these pebbles back to 4m−1,d such that they are in sorted order (according to
π).
3. Sort the mesh Mm−1 according to πm−1 .
4. Route a pebble of rank i ≤ nm−2 at position xi ∈ Mm−1 to yi ∈ Mm−1 where
−1
yi [j] = 2πm−2
(nm−2 + 1 − i)[j] − 1

Let Y = (y1 , . . . , ynm−2 ).
14

5. Merge Y with Mm−2 using pair-wise compare-exchanges, where yi is compared with
z ∈ Mm−2 such that πm−2 (z) = i.
6. Repeat 1-5.
7. Repeat 1-3.
Running time Note that the number of times we route on 4m,d is 6. Also sorting on
the mesh Mm−1 occurs 6 times. We know that both routing and sorting on a mesh takes
O(dN 1/d ) steps. From Lemma 6.5 we see that routing on 4m,d also takes O(dN 1/d ) steps.
So the total contribution of all the steps except 4 and 5 is O(dN 1/d ). It is easy to see that
step 4 also takes O(dN 1/d ) and the step 5 can be accomplished in constant time. Putting it
all together we see that st(4m,d ) = O(dN 1/d ) as claimed.
Proof of correctness Next we give proof sketch that S(4m,d , M, π) is a sorting network.
Clearly the algorithm is oblivious, hence we invoke the 0-1 principle [7] and assume that
our pebbles are all 1’s and 0’s. Before the execution of step 7 if every pebble in 4m−1,d is
smaller than every pebble in Mm−1 then after step 7 we shall have our desired sorted order.
So lets assume to the contrary it is not. Then there must be some pebbles x ∈ Mm−1 that
suppose to be in 4m−1,d . If that is the case then x must be a 0 otherwise x is ≥ every
pebble in 4m−1,d and we are done. Now let us look at step 4 and 5. In step 4 we route the
set of nm−2 smallest pebbles in Mm−1 such that the ith smallest pebble is at some vertex of
Mm−1 which is directly connected to the vertex in Mm−2 that has the ith largest pebble of
Mm−2 . Since x was not exchanged during both the iteration of step 4 and 5 then x must be
larger than at least 2nm−2 elements in 4m,d , but then x should not belong to 4m−1,d (since
|4m−1,d | ≤ 2nm−2 − 1 for any d) contradicting our assumption. Hence, after step 6 we see
that all pebbles of 4m−1,d must be smaller than every pebble of Mm−1 hence sorting these
pebbles independently in the final step gives the desired sorted order.

References
[1] Miklós Ajtai, János Komlós, and Endre Szemerédi. An 0 (n log n) sorting network.
In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages
1–9. ACM, 1983.
[2] Noga Alon, Fan RK Chung, and Ronald L Graham. Routing permutations on graphs
via matchings. SIAM journal on discrete mathematics, 7(3):513–530, 1994.
[3] O. Angel and I. Shinkar. A tight upper bound on acquaintance time of graphs. Graphs
and Combinatorics, 32(5):1667–1673, 2016. arXiv:1307.6029.
[4] László Babai and Mario Szegedy. Local expansion of symmetrical graphs. Combinatorics, Probability and Computing, 1(01):1–11, 1992.
15

[5] Kenneth E Batcher. Sorting networks and their applications. In Proceedings of the April
30–May 2, 1968, spring joint computer conference, pages 307–314. ACM, 1968.
[6] Itai Benjamini, Igor Shinkar, and Gilad Tsur. Acquaintance time of a graph. SIAM
Journal on Discrete Mathematics, 28(2):767–785, 2014.
[7] D.E. Knuth. The art of computer programming: Sorting and searching. The Art of
Computer Programming. Addison-Wesley, 1998.
[8] Manfred Kunde. Optimal sorting on multi-dimensionally mesh-connected computers.
In Annual Symposium on Theoretical Aspects of Computer Science, pages 408–419.
Springer, 1987.
[9] F Thomson Leighton. Introduction to parallel algorithms and architectures: Arrays ·
trees · hypercubes. Elsevier, 2014.
[10] Tom Leighton and C Greg Plaxton. Hypercubic sorting networks. SIAM Journal on
Computing, 27(1):1–47, 1998.
[11] C. Greg Plaxton and Torsten Suel. A super-logarithmic lower bound for hypercubic sorting networks. In International Colloquium on Automata, Languages, and Programming,
pages 618–629. Springer, 1994.
[12] Claus Peter Schnorr and Adi Shamir. An optimal sorting algorithm for mesh connected
computers. In Proceedings of the eighteenth annual ACM symposium on Theory of
computing, pages 255–263. ACM, 1986.

16

