  The sorting number of a graph with $n$ vertices is the minimum depth of a
sorting network with $n$ inputs and 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.
  Any $n$-vertex graph that contains a simple path of length $d$ has a sorting
network of depth $O(n \log(n/d))$.
  Any $n$-vertex graph with maximal degree $\Delta$ has a sorting network of
depth $O(\Delta n)$.
  We also provide several results that relate 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.
