《算法導論》7-3看到了這個好東東，beautiful-sort，代碼確實漂亮。不愧是教授啊，Howard，Fine，膜拜ing.
int stooge_sort(int a[],int s,int t)
{
int k;
if (a[s]>a[t])
swap(a[s],a[t],k);
if (s+1>=t)
return 0;
k=(t-s+1)/3;
stooge_sort(a,s,t-k);
stooge_sort(a,s+k,t);
stooge_sort(a,s,t-k);
}
a) 證明：如果n=Length[A]，那么STOOGE-SORT(A, 1, Length[A])能正確地對輸入數組A[1..n]進行排序。
循環不變式：過程STOOGE-SORT(A, i, j)被調用后，數組A中[i, j]區間內的元素是有序的。
初始化：i+1>=j時，[i, j]區間中只有一個或者兩個元素，唯一的操作就是 if A[i]>A[j] then exchange A[i]<->A[j]，顯然循環不變式是成立的。
保 持：每一次STOOGE-SORT(A, i, j)被調用時，假設循環不變式成立。則調用STOOG-SORT(A, i, j-k)使得區間[i, j-k]有序，調用STOOG-SORT(A, i+k, j)使得區間[i+k, j]有序。因為k=(j-i+1)/3，所以區間[i, j-k]和區間[i+k, j]的重疊部分區間[i+k, j-k]的元素個數為[i, j]中元素個數的1/3，也為k個。因調用STOOG-SORT(A, i, j-k)后區間[i, j-k]有序，所以區間[i+k, j-k]中的元素應該是區間[i, j-k]中最大的k個元素，于是調用STOOG-SORT(A, i+k, j)后可以保證區間[j-k+1, j]中包含區間[i, j]中最大的k個元素并且是有序的。因此可保證在第二次調用STOOG-SORT(A, i, j-k)后區間[i, j]有序。
終止：STOOGE-SORT(A, i, Length[A])調用結束后，根據循環不變式，數組A中的元素是有序的。
b) 給出一個表達STOOGE-SORT最壞情況的運行時間的遞歸式，以及關于最壞情況運行時間的一個緊確的漸進（Θ記號）界。
T(n)=3T(2n/3)+Θ(1)
根據主定理：
a=3 b=3/2 f(n)=Θ(1)
故有 f(n)=O(n^log(3/2, 3-ε)) (ε>0)
所以 T(n)=Θ(n^log(3/2, 3))>Θ(n^2)
復制了大牛的文章過來，沒事自己看看。
不過怎么覺得Thomas.H.Cormen等人有點諷刺諷刺這幾個教授呢？？