1
$\begingroup$

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 
  • 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.2012-04-16

1 Answers 1

1

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