Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
1  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.