# How to calculate the depth of sorting networks?

I have trouble understanding how to calculate the depth of a sorting network on $n$ inputs.

For example, in case of selection sort, we have:

$\qquad \displaystyle D(n)=D(n-1)+2\\\qquad D(2)=1$

which leads to

$\qquad \displaystyle D(n)=2n-3=\Theta(n)$

I have confirmed that the depth of selection sort is equal to $2n-3$ by hand, but I can't understand how the recurrence $D(n)=D(n-1)+2$ is derived.

-

## migrated from cstheory.stackexchange.comJul 29 '12 at 20:22

This question came from our site for theoretical computer scientists and researchers in related fields.

Welcome! I am confused as to what is being asked here. Are you asking how to read a recurrence, or why this recurrence applies to selection sort? Do you have a sorting network implementation of selection sort at hand, or are you talking about the algorithm and its recursion depth? – Raphael Jul 29 '12 at 21:45
Have you tried drawing a picture of the selection-sort sorting network? What does it look like? – JeffE Jul 30 '12 at 2:54

## 1 Answer

For selection/bubble sorting network algorithms, the main tricky point is that "some operations are overlapped" or in other words because of pipeling! (it is shown in figure below) You can find more information in these lecture notes by Rolf Karlsson.

This is the reason why the time complexity is linear!

-
I'm not sure pipelining (as seen in processors?) is a good analogy here; it's more like perfect parallelism, isn't it? – Raphael Feb 3 '13 at 1:23
@Raphael: I changed the picture which shows the pipeline concept better! – Reza Feb 3 '13 at 3:19