# Explaining an algorithm

Regarding this algorithm:

Algo(A, p, r)
if p ≤ r then
q ← Partition(A,p,r)
if q == r then
return A[q]
else
return Mystery(A,q+1,r)
end
end


While partition is:

Partition(A,p,r)
x=A[r]; j=r; i=p-1;
While true
repeat j ← j - 1
until A[j]<x
repeat i ← i +1
until A[i] >= x
if i<j
then A[i] ←→ A[j] % swap
else A[j+1] ←→ A[r]
return j+1


I need to explain what Algo do.

So Partition is from Quicksort, dealing with the pivot.

Partition basically returns the index of the pivot, and then in Algo, we are taking the index and assigning it into q.

We are keep doing it until q==r, but I don't understand what Algo really does, is the output, and what is the running time of something like this.

Any help will be amazing!

Thanks a lot!

• What is the Mystery function? Is it the same as Algo? – Nathaniel Apr 28 at 17:38
• It's a... Mystery ;) – Steven Apr 28 at 18:29