There is a sorting algorithm, Stooge-Sort which is named after the comedy team, "The Three Stooges." if the input size, n, is 1or 2, then the algorithm sorts the input immediately. Otherwise, it recursively sorts the first 2n/3 elements, then the last 2n/3 elements, and then the first 2n/ 3 elements again. The details are shown in Algorithm below.

Algorithm StoogeSort(A, i, j ):

Input: An array, A, and two indices, i and j, such that 1 i j < n

Output: Subarray, A[i..j] ,sorted in nondecreasing order

1. n j i + 1 // The size of the subarray we are sorting

2. if n = 2 then

3. if A[i] > A[j] then Swap A[i] and A[j]

4. else if n > 2 then

5. m n/3

6. StoogeSort(A, i, j-m) // Sort the 1^st part.

7. StoogeSort(A, i+m, j) // Sort the last part.

8. StoogeSort(A, i, j-m) // Sort the 1^st part again.

9. return A

[10, Optional] Show that Stooge-sort is correct by Mathematical induction.

[10] Characterize the running time, T (n) , for Stooge-sort, using a recurrence equation.

[10] By means of Masters Theorem, determine an asymptotic bound for T (n).

[10, Optional] Solve the recurrence equation in 2 by means of Iterative Substitution method.

[10] Suppose we change the assignment statement for m (on line 5) to the following:

m max {1, n/4

[5] Characterize the running time, T(n), in this case, using a recurrence equation.

[5] Using the Masters Theorem, decide the asymptotic bound for T(n) in (A).