快速排序的分割（quicksort partition）

快速排序用的技巧和合併排序不同：它不是盲目地從中間切開、在合併時做巧妙工作，而是在切分時就把巧妙工作做掉，於是合併時無事可做。關鍵運算是分割（partition）：挑一個元素當樞紐（pivot），然後重排陣列，使比樞紐小的元素都落在它左邊、較大的都落在右邊。此時樞紐已位於它最終的排序位置，你便對左部與右部各自獨立遞迴。

以 Lomuto 分割對 [3,7,1,5 | 樞紐=4] 用白話步驟說明（樞紐在常見版本中取最後一個元素；此處以 4 示意）：讓指標 i 走過陣列，維持「邊界左邊的東西都 < 樞紐」這個不變量。每遇到 < 樞紐的元素就交換到邊界之後；>= 樞紐的元素則略過。經一趟線性 O(n) 掃描後，陣列被分成 [< 樞紐][樞紐][>= 樞紐]，並回傳樞紐的索引。接著快速排序對兩側各自呼叫自己。因為分割把樞紐正確就位、兩側又是分別獨立排序的互不重疊切片，陣列最終就排好了——根本沒有合併步驟。

當樞紐大致把陣列對半切時，遞迴關係式為 T(n) = 2 T(n/2) + O(n) = O(n log n)，實務上快速排序常是最快的記憶體內排序，因為分割對快取友善且原地（只需 O(log n) 堆疊空間）。但誠實的告誡是最壞情況：若每個樞紐都是最小或最大元素——例如對已排序輸入用樸素的「取最後一個」當樞紐——分割每次只剝掉一個元素，給出 T(n) = T(n-1) + O(n) = O(n^2)。這正是樞紐通常以隨機或三數取中（median-of-three）來選的原因，使壞情況變得天文數字般罕見。