= Stooge sort
{title2=$T(n)=\Theta(n^{\log_{3/2}3})$}
{wiki}
First exchange the endpoints of the current subarray if they are out of order. For current length $m>2$, put $k=\lfloor m/3\rfloor$ and recursively sort its first $m-k$ entries, its last $m-k$ entries, then its first $m-k$ entries again. Each child has length $\lceil2m/3\rceil$; the split must use the current subproblem length. The <master theorem> gives exponent $\log_{3/2}3\approx2.7095$, worse than quadratic. The usual algorithm is not stable: endpoint exchange on $[2_a,2_b,1]$ leaves the equal-key records reversed after sorting.
Back to article page
