# 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

## 1 Answer

The basic idea seems to be to do something like merge sort but avoid actually merging. To do this we essentially first sort the first 2/3rd of the array, then the next 2/3, and then the first 2/3rd again. The important thing is that after the first two steps, anything that should lie in the last 1/3 of the sorted array gets there (so the third step sorts the rest and then we are done). To see this, note that anything that is among the top 1/3 of the elements is in the second half of the first 2/3 after the first step (as less than 1/3 of the elements are more than it), and so it is also affected by the second step.

Running time: T(2) = c1 (constant).

T(n) = 3T(2n/3) + c2.

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

-