2
$\begingroup$

I was learning about recursion and i came across the following pseudo code for quicksort.

QUICKSORT(A,p,r)
1   if p < r
2      then q := PARTITION(A,p,r)
3           QUICKSORT(A,p,q-1)
4           QUICKSORT(A,q+1,r)

In this code there are two consecutive statements that recursively call quicksort function. It confuses me. I want to know how these statements gets executed. Does the partition of left half of the array happens recursively or does both left and right of the array gets partitioned at the same time?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Depends on the semantics of the language, of course. $\endgroup$ – Raphael♦ Jun 5 '16 at 11:03
  • $\begingroup$ maybe some of this question relates to the concept of local variables and the stack. try learning how the code translates into those concepts. (there are some demonstrations of this around.) it does show how many sophisticated concepts are implicit even in mere pseudocode. $\endgroup$ – vzn Jun 5 '16 at 14:13
5
$\begingroup$

Just like any other two consecutive statements in an ordinary programming language, they're executed one after the other.

However, since the two recursive calls operate on disjoint sections of the array, you could, in principal, execute them in parallel.

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ I just realized that the obvious answer (this one) is so obvious only because sequential execution has been hammered into our brains for decades. This may be the root of many problems with parallel programming, among other things. $\endgroup$ – Raphael♦ Jun 5 '16 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.