Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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
share|cite|improve this question
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

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}$)

share|cite|improve this answer

Your Answer


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

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