# Yet another sorting algorithm

Computer Science Level pending
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def floor(n): """Compute the floor function of n""" return int(n) def stoogy(A, i, j): """Sort A[i...j]""" if A[i] > A[j]: A[i] , A[j] = A[j] , A[i] #Swap A[i] and A[j] if i + 1 >= j: return m = floor( (j - i + 1) / 3) stoogy(A, i, j - m) stoogy(A, i+m, j) stoogy(A, i, j - m) def sort(A): """Sort the list A[0..n]""" stoogy(A, 0, len(A) - 1) 

The tight asymptotic bound of ($$\Theta$$ - notation) of the sorting algorithm above(sort(A)) can be expressed as $$\Theta(n^{\alpha})$$( $$\alpha \in \mathbb{R}$$ ). Find $$\alpha$$.

Details and Assumptions

• $$n$$ is the size of the array to be sorted.
×