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