不一定，要看你排序的資料是什麼。如果是大小有上限的自然數，或者長度有限的字串的話，用基數排序或者Burstsort，n個輸入只需要O(n)的時間，當然，具體的乘法常數依賴於自然數的上限和字串的長度。
但這些是有點耍賴的排序方式：它們並沒有比較元素本身的大小，而是取元素的一小部分，根據特殊性質來進行排序。如果我們不允許這樣的行為，規定排序中只能有兩種操作，比較兩個元素的大小，還有交換兩個元素，那麼，加上這樣的限定之後，我們得到的就是所謂的“比較排序”。無論是快速排序、歸併排序，都屬於一種比較排序，而比較排序的時間複雜度的確不會低於O(n log n)。
這樣的證明在計算機演算法中，屬於下界分析的範疇。我們來看看怎麼對一般的比較排序進行下界分析。假設我們要用比較排序演算法A對n個元素進行排序。
首先，我們假設元素互不相同，所以元素之間的比較只有兩個結果。那麼，在A執行時，它做的事情就都由這些比較的結果決定。我們可以用二叉樹來模擬這些比較：樹根是第一次比較（之前可能有別的操作，但結果是一樣的），然後根據比較的兩種不同結果，演算法A會走向左邊或者右邊的子結點，途中可能會執行一些操作，最終到達某一個子結點，也就是下一次比較。注意，不同的子結點進行的比較不一定相同。這樣繼續執行下去，最終A會到達某個葉子，停止執行，這時所有元素都應該排好序了。
也就是說，演算法A可以看成一棵二叉樹T，每個結點都是一次比較，而根據比較的結果是大是小，演算法會繼續執行相應的步驟，直到遇上另一次比較，就這樣一直下去，直到到達葉子。
那麼，T有多少片葉子呢？
T的葉子數目不能少於n!（n的階乘）。這是因為，n個元素有n!種不同的排列可能性，每一種都需要不同的元素交換方式來完成排序（當然，對於同一個排列，可以有多種不同的交換方式），但每片葉子對應的交換方式是唯一的，因為從樹根到葉子的路徑是唯一的。所以，葉子至少要有n!片，才能“裝下”所有n!種可能性。
但如果演算法A至多需要h次比較的話，也就是說T的高度至多是h+1的話，我們知道，高度為h+1的二叉樹最多有2^h - 1片葉子。所以，我們有下面的不等式：
2^h - 1 >= n!
因為我們要涉及很大的n，所以-1幾乎可以忽略。取斯特林近似ln(n!) = sqrt(2n\pi) (n/e)^n，我們得到：
h >= n log n - n * log(e) + O(1)
所以，h的量級至少是O(n log n)。
比較排序是下界分析最典型的例子之一。下界分析能揭示最壞情況的時間複雜度，但要知道平均情況的時間複雜度就麻煩得多，通常需要藉助所謂分析組合學（analytic combinatorics）的力量。
不一定，要看你排序的資料是什麼。如果是大小有上限的自然數，或者長度有限的字串的話，用基數排序或者Burstsort，n個輸入只需要O(n)的時間，當然，具體的乘法常數依賴於自然數的上限和字串的長度。
但這些是有點耍賴的排序方式：它們並沒有比較元素本身的大小，而是取元素的一小部分，根據特殊性質來進行排序。如果我們不允許這樣的行為，規定排序中只能有兩種操作，比較兩個元素的大小，還有交換兩個元素，那麼，加上這樣的限定之後，我們得到的就是所謂的“比較排序”。無論是快速排序、歸併排序，都屬於一種比較排序，而比較排序的時間複雜度的確不會低於O(n log n)。
這樣的證明在計算機演算法中，屬於下界分析的範疇。我們來看看怎麼對一般的比較排序進行下界分析。假設我們要用比較排序演算法A對n個元素進行排序。
首先，我們假設元素互不相同，所以元素之間的比較只有兩個結果。那麼，在A執行時，它做的事情就都由這些比較的結果決定。我們可以用二叉樹來模擬這些比較：樹根是第一次比較（之前可能有別的操作，但結果是一樣的），然後根據比較的兩種不同結果，演算法A會走向左邊或者右邊的子結點，途中可能會執行一些操作，最終到達某一個子結點，也就是下一次比較。注意，不同的子結點進行的比較不一定相同。這樣繼續執行下去，最終A會到達某個葉子，停止執行，這時所有元素都應該排好序了。
也就是說，演算法A可以看成一棵二叉樹T，每個結點都是一次比較，而根據比較的結果是大是小，演算法會繼續執行相應的步驟，直到遇上另一次比較，就這樣一直下去，直到到達葉子。
那麼，T有多少片葉子呢？
T的葉子數目不能少於n!（n的階乘）。這是因為，n個元素有n!種不同的排列可能性，每一種都需要不同的元素交換方式來完成排序（當然，對於同一個排列，可以有多種不同的交換方式），但每片葉子對應的交換方式是唯一的，因為從樹根到葉子的路徑是唯一的。所以，葉子至少要有n!片，才能“裝下”所有n!種可能性。
但如果演算法A至多需要h次比較的話，也就是說T的高度至多是h+1的話，我們知道，高度為h+1的二叉樹最多有2^h - 1片葉子。所以，我們有下面的不等式：
2^h - 1 >= n!
因為我們要涉及很大的n，所以-1幾乎可以忽略。取斯特林近似ln(n!) = sqrt(2n\pi) (n/e)^n，我們得到：
h >= n log n - n * log(e) + O(1)
所以，h的量級至少是O(n log n)。
比較排序是下界分析最典型的例子之一。下界分析能揭示最壞情況的時間複雜度，但要知道平均情況的時間複雜度就麻煩得多，通常需要藉助所謂分析組合學（analytic combinatorics）的力量。