# Divide and conquer - Algorithm MYST

i am trying to understand the following algorithm. It is a divide and conquer algorithm, which sorts a given array, but can someone help me to understand the idea of this algorithm. What is the running time of it and why?

Thanks

procedure MYST(A, l, r)

range := r − l + 1

//returns the least integer greater or equal to x - ceiling function of [x]
subrange := [2 · range/3]

if range = 2 and A[l] > A[r] then

swap A[l] ↔ A[r]

else if range ≥ 3 then

MYST(A, l, l + subrange − 1)

MYST(A, r − (subrange − 1), r)

MYST(A, l, l + subrange − 1)

end if

end procedure

-
FWIW a trivial variant on this algorithm is stooge sort, and the question is equivalent to exercise 8-3 of Introduction to Algorithms by Cormen, Leiserson, and Rivest. – Peter Taylor Apr 16 '12 at 20:25

So by the master theorem, T(n) = O($n^{log_{3/2}3}$)