n log n 時間
在純線性時間 Theta(n) 與平方時間 Theta(n^2) 之間，坐著一個極為重要的中間級：Theta(n log n)，讀作「n log n」，常稱為線性對數時間。它是最佳通用排序演算法、以及無數分治法的執行時間，所以值得把它當作獨立的地標來理解，而非一個註腳。
函數 n log n 只比線性高一點點，因為對數成長得如此緩慢：對 n = 1,000,000，log2(n) 約為 20，所以 n log n 約為兩千萬——只是一百萬線性成本的二十倍，而非一百萬倍。這就是為什麼 n log n 演算法在實務上感覺幾乎和線性一樣快，並遠快於平方的。這個形狀自然地來自分治：若你把規模 n 的問題切成兩半、遞迴、再花線性時間合併，就得到一個解為 Theta(n log n) 的遞迴關係式——大約有 log2(n) 層對半切，每層共做 Theta(n) 的工作，所以乘積是 n log n。合併排序是課本上的範例。
n log n 之所以重要，是因為對許多問題它就是你能做到的最好：以比較為基礎的排序有一個已證的 Omega(n log n) 下界，所以合併排序與堆積排序在該模型內是漸進最佳的——你無法靠巧計勝過 n log n，只能靠改變模型（例如對小整數用計數排序）。當你看到 n log n，就把它記成「本質上線性、外加一個小小的對數附加費」，是大規模處理的甜蜜點。
對 n 個項目做合併排序：切成兩半（共 log2(n) 層切割），每一層的合併合起來把全部 n 個項目各碰一次，每層花 Theta(n)。總工作 =（層數）乘（每層工作）= log2(n) 乘 n = Theta(n log n)。
約 log n 層、每層做 Theta(n) 工作，相乘即 n log n。
比較式排序無法勝過 Omega(n log n)，所以 n log n 在此是最佳的；更快的排序（如計數排序）只能藉由跳出比較模型而存在，而非更聰明地比較。