Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Jul 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 1

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! enter image description here

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.