# 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$

$\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.

-
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

## 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.