Stooge-sort

Stooge-sort(A, i, j)
if A[i] > A[j]
then exchange A[i], A[]
if i + 1 >= j
then return
k = (j - i + 1) / 3
Stooge-sort(A, i, j - k)
Stooge-sort(A, i + k , j)
Stooge-sort(A, i, j - k)
即先排序前2/3部分，然后是后2/3部分，最后再进行前面1/3的排序。

a. 证明算法正确性
由于是递归算法，而初始状态显然成立，因此只要证明当部分排序正确时，整体也能够被正确排序：
第一次排序后，第二部分每个数都不小于第一部分的所有数；
第二次排序后，第二部分某些数被交换到第三部分中，此时第三部分数都不小于第二部分和第一部分的数，但是第二部分的数并不一定都小于第一部分的（因为可能包含第三部分的数，而这些数与第一部分数的大小关系无法确认）；
第三次排序后，第二部分的数都不小于第一部分的数。
这样，第一部分的任意数<=第二部分的任意数<=第三部分的任意数
而且各部分的数都已排序，因此整体已被排序。

b. 复杂度分析
递归式
T(n) = 3T(2n/3) + 1
由Master Theorem
T(n) = O(n^log(3/2, 3))