天秤找假幣（四）

完成這個系列，我說說這個方法在計算機科學（Computer Science）的應用。

曾經有人說過，電腦有超過六成的時間是用來做排序（sorting）的。排序是指有一些不跟次序排列的數字，要根據遞升/遞降（ascending order/descending order）排好。當然實際上要排序的東西可以很多，例如字串（string）、集合（set）等，但在此不作討論。因為電腦用來做排序的時間很多，所以我們很希望想一些算法（algorithm）出來減少其運算時間。歷史上很快就找到一些O(n lg n)的comparison-based sorting方法，如配合binary search的insertion sort、merge sort等。但，有沒有更快的方法呢？

所謂comparison-based sorting，就是每次只可以比較兩個數字a和b，很到的結果是 a<= b是TRUE還是FALSE。 假設現在有n個未排好的數字，則它們的n! permutations都是有可能成為排序後的次序的。若使用樹形圖的概念，這即是說該樹形圖最少要有n!個「黃色格」。而因為每次比較的結果只有兩個可能性，故要達到有n!個「黃色格」，最少要有 log₂(n!) 層，亦即最少要做 log₂(n!) 次comparisons。根據Stirling's Formula， log₂(n!) 約等於 n ln (n) / ln 2 。這證明了 comparison-based sorting需要最少 O(n ln n) 時間。

P.S.: 這裏使用了一個叫"Big-Oh"的notation，未見過的人可在此參考。