首先说排序算法时间复杂度的极限是$O(n)$。这点可以从信息论的角度考虑：你要排序一个数组，你至少要知道它们每个都是什么，所以必然要遍历数组。这就使得算法的时间复杂度至少为$O(n)$。因为这是必要的信息。

同理可以考虑比较排序的方法：每次比较我们得到的信息是$3$种（大于、小于、等于），但由于等于这种信息不会对排序造成影响（事实上，它可以和大于或者小于放在一起）。这样我们就得到$2$种可能性。$n$个元素所有可能性的复杂度是$O(n!)$。$n$次比较的复杂度是$O(2^n)$。二者相除，通过一些数学可以知道，比较次数复杂度是$O(n\lg{n})$。

用这种方法，我们也可以知道，为什么乱序的数组，找到一个元素时间复杂度是$O(n)$，而排好序的数组只需要$O(\lg{n})$次。