前言

昨天的 Merge Sort 用分而治之確保每次執行都是 O(N log N)，代價是每次合併都要一個新陣列來裝結果，額外空間是 O(N)。那如果新陣列是合併造成的，有辦法乾脆不要合併嗎？不要合併就沒有新陣列的問題😌

但不合併的話，左右兩半各自排好後，要怎麼變成一份完整排好的陣列？除非有一個條件已成立：左半邊的每一個元素本來就都小於右半邊的每一個元素。若成立，兩半各自排好，接在一起就已經是排好的了，不必再做任何比較。Merge Sort 無法確保這條件，因為它是照位置對半切的，切在哪裡和值是多少無關。

那有沒有辦法在拆的時候就換一種切法，切出來剛好滿足這個條件呢？今天的 Quick Sort 就是這樣做的～

Quick Sort：排序發生在拆分的那一步

先給 Quick Sort 一句話定義：

Quick Sort（快速排序）從陣列裡挑出一個元素當作 pivot，把比它小的元素移到左側、其餘移到右側，讓 pivot 落在它最終排序後的位置，接著對左右兩側各自重複同一件事。

Quick Sort 和 Merge Sort 都利用分而治之的概念，差別在成本落在哪一步。比較兩者的三個步驟，差別如下：

Merge Sort 的 divide 成本很低，算一次中點就好，成本集中在 combine，要走過這一層全部的元素、還要創一個新陣列。Quick Sort 把成本整個挪到前面，它的 divide 要走過全部的元素，換來的是 combine 什麼都不用做，因為分完之後左側每一個都小於 pivot、右側每一個都大於或等於 pivot，兩側各自排好就直接接得起來。

Quick Sort 的通用步驟

Quick Sort 每次處理一段陣列，可以拆成四步：

1. 如果這段陣列只剩 1 個元素或是空的，它本來就是排好的，什麼都不用做，這一層就到此結束
2. 否則從這段陣列裡挑一個元素當作 pivot
3. 把這段陣列重新排列，讓 pivot 停到某一格，它左邊的元素都比它小、右邊的都大於或等於它，並記下這一格是第幾格
4. 對 pivot 左邊那段和右邊那段，各自從第 1 步再做一次

和 Merge Sort 一樣，第 4 步指回自己，因此同一套步驟會往下作用在越來越小的兩段上。而真正的工作集中在第 3 步，它有個名字叫 partition。

Pivot 與 Partition

Pivot：用來分界的那個元素

先看 pivot 是什麼：

Pivot（基準點）是每一輪從當前這段陣列裡挑出來、用來把其他元素分到兩側的那個元素。

pivot 可以挑這段陣列裡的任何一個元素，挑法不影響正確性，只影響快慢。這裡固定挑最後一個元素作為 pivot，實作上最單純。這種「拿最後一格當 pivot、用單一索引往前掃」的分割寫法有個名字叫 Lomuto partition，本篇從頭到尾都用這一種來介紹；如果在網路資源有看到左右兩個指標對撞的版本，那是另一種寫法，步驟和下面講的不同。

今天的主要範例會用 [8, 3, 1, 7, 0, 10, 2]，最後一個是 2，所以第一輪的 pivot 就是 2。

Partition 要達成的事

Quick Sort 通用步驟第三步是 partition，partition 跑完後，要讓三件事同時成立：

1. pivot 停在某一格，記下這一格的索引，叫做 partitionIndex
2. partitionIndex 左邊的每一格都小於 pivot
3. partitionIndex 右邊的每一格都大於或等於 pivot

為什麼要特地把 pivot 停的那一格記下來呢？既然左邊全部都比 pivot 小、右邊全部都不比它小，那不管左右兩側之後怎麼排、內部怎麼換位置，排在 pivot 前面的永遠是那些比它小的元素、排在後面的永遠是其餘的元素。也就是說，pivot 現在停的那一格，就是整個陣列完全排好後它會在的那一格，就再也不會移動。這正是 combine 什麼都不用做的原因。

圖 1 partition 跑完後，pivot 已經在最終位置，兩側各自還是亂的

那要怎麼在不使用新陣列空間的前提下，一次掃描就達成這三件事呢？先來看看 Partition 運作流程吧～

Partition 的通用步驟

partition 每次處理一段陣列，可以拆成四步：

1. 拿這段的最後一格當 pivot，另外準備一個 partitionIndex，一開始指向這段的左界
2. 用另一個索引 i 從左界往右掃，掃到 pivot 前一格為止
3. 每掃到一格只做一件判斷：array[i] 小於 pivot 的話，就把它和 array[partitionIndex] 對調，然後 partitionIndex 往右移一格；大於或等於的話什麼都不做
4. 掃完之後，把 pivot 和 array[partitionIndex] 對調，並回傳 partitionIndex

partitionIndex 這變數的意思是「下一個小於 pivot 的元素應該放進來的位置」。

走一次 partition

拿主例 [8, 3, 1, 7, 0, 10, 2] 來走一次 partition。這一輪處理的是整段 [8, 3, 1, 7, 0, 10, 2]，pivot 是最後一格的 2，i 和 partitionIndex 都從 index 0 出發，i 只掃到 index 5，因為最後一格是 pivot 本身：

1. i = 0，array[0] 是 8，8 >= 2，什麼都不做。partitionIndex 還是 0
2. i = 1，array[1] 是 3，3 >= 2，什麼都不做。partitionIndex 還是 0
3. i = 2，array[2] 是 1，小於 2，和 array[0] 對調，陣列變成 [1, 3, 8, 7, 0, 10, 2]，partitionIndex 從 0 變成 1
4. i = 3，array[3] 是 7，7 >= 2，什麼都不做
5. i = 4，array[4] 是 0，小於 2，和 array[1] 對調，陣列變成 [1, 0, 8, 7, 3, 10, 2]，partitionIndex 從 1 變成 2
6. i = 5，array[5] 是 10，10 >= 2，什麼都不做

掃完之後陣列是 [1, 0, 8, 7, 3, 10, 2]，partitionIndex 停在 2，此時 index 0 和 1 的 1 和 0 都小於 2，index 2 到 5 的 8、7、3、10 則都大於或等於 2。現在還差最後一件事，pivot 還躺在最後一格沒動。

最後補一次交換，把 pivot 和 array[partitionIndex] 對調，也就是把 index 6 的 2 和 index 2 的 8 換過來，得到 [1, 0, 2, 7, 3, 10, 8]，然後回傳 partitionIndex 的值 2。

圖 2 一次 partition 的每一步，未掃描區一格一格被較小區和較大區吃掉

Partition Invariant：每一輪都維持的兩句保證

剛才那一趟確實跑出了想要的結果，2 抵達了最終的正確位置，但那只是一組輸入而已。要怎麼確定 partition 拿到任何一段陣列都運作正確呢？

關鍵在掃描進行到一半的時候。i 掃到哪裡，pivot 以外的部分就被 partitionIndex 和 i 切成三塊：partitionIndex 左邊是較小區，每一格都確定小於 pivot；partitionIndex 到 i 之間是較大區，每一格都確定大於或等於 pivot；i 到 pivot 之間是未掃描區，還不知道那些值和 pivot 的大小關係。掃描要做的就是把未掃描區一格一格吃掉，同時讓前兩區維持各自的性質。

partition 的做法可以用 Day 04 的 loop invariant 來描述：

在每一輪開始之前，partitionIndex 左邊的每一格都小於 pivot，而 partitionIndex 到 i 之間的每一格都大於或等於 pivot。

用 Day 04 那套三步法來看看。

Initialization：第一輪之前還沒掃到任何元素，partitionIndex 和 i 都停在這段陣列的左界，兩句話的範圍都是空的，空的範圍要滿足什麼條件都自動成立，因此兩句在第一輪之前都是真的。

Maintenance：假設兩句話在這一輪之前成立，要推出它們在下一輪之前也還成立。如果 array[i] 大於或等於 pivot，它本來就該待在較大區，什麼都不用做，partitionIndex 不動，等於較大區自己往右長了一格，兩句話當然都還成立。

如果 array[i] 小於 pivot，就把它和 array[partitionIndex] 對調，也就是和較大區的第一格互換。這一格因此進到較小區，而被換走的那個原本就大於或等於 pivot，跑到 i 的位置仍然留在較大區裡，兩區各自的性質都沒被破壞。接著 partitionIndex 往右移一格，較小區多了一個確定小於 pivot 的元素、界線也跟著往右一格，兩件事一起發生，invariant 就繼續成立。

圖 3 Maintenance 的兩種情況，不管換或不換，兩句保證都還成立

為什麼最後那次交換一定落在交界處

partition 收尾的交換看起來有點取巧，把 pivot 硬塞進 partitionIndex，被擠掉的那個元素直接丟到最後一格，怎麼會剛好是對的呢？

Termination：迴圈結束時 i 已經走到 pivot 前面，未掃描區空了，pivot 以外的部分只剩較小區和較大區兩塊，中間沒有縫隙。因此 partitionIndex 這一格必定是較大區的第一格，它的值大於或等於 pivot，把它換到最後一格去，它仍然待在較大區裡，位置合法；而空出來的 partitionIndex 給了 pivot，它左邊全部更小、右邊全部不更小，三件事就一起成立了。

還有一個邊界狀況，如果整段裡沒有任何元素小於 pivot，迴圈跑完 partitionIndex 還停在左界，收尾的交換就是把 pivot 換到最前面，代表 pivot 是這段裡最小的，左側是空的。反過來如果每一個元素都小於 pivot，partitionIndex 會一路推到最後一格，收尾等於把 pivot 和自己交換，陣列沒有變，代表 pivot 是最大的，右側是空的。兩種極端都不需要另外寫程式處理，這也是 partitionIndex 這個寫法好用的地方。

遞迴處理左右兩側

用索引傳範圍，不切出新陣列

partition 回傳 partitionIndex 後，接下來要對左右兩側各做一次同樣的事，而這裡有一個和 Merge Sort 不一樣的地方：不要用 slice 切出兩側。

昨天的 mergeSort 每一層都 slice 出左右兩段，所以呼叫端傳進來的陣列從頭到尾沒被動過，代價是每一層都重新配置一份空間。Quick Sort 則相反，它從頭到尾只用同一個陣列，靠 left 和 right 兩個索引表示「現在在處理哪一段」。左側是 left 到 partitionIndex - 1，右側是 partitionIndex + 1 到 right，pivot 那一格已經定位，兩邊都不含它，每次遞迴的範圍一定比原本短，遞迴一定會停止。

也就是說，前言那個「不要新陣列」的目標，是靠 partition 原地交換加上用索引傳範圍這兩件事一起達成的。更進一步來說，Quick Sort 是拿「原始陣列會被改動」換掉那份額外空間，而這就是原地排序 (in-place sort)。

寫成程式

Quick Sort 寫成程式如下：

function quickSort(array, left, right) {
  // 這段有 2 格以上才要處理，left >= right 是只剩 1 格或空的，本來就排好了
  if (left < right) {
    // 分割目前這段，回傳 pivot 的最終位置
    const partitionIndex = partition(array, left, right);

    // pivot 已經定位，左右兩側都不含它
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
  }

  return array;
}

function partition(array, left, right) {
  const pivotValue = array[right]; // 固定拿最後一格當 pivot
  let partitionIndex = left; // 下一個「小於 pivot」的元素該放的位置

  // 掃到 pivot 前一格就停，最後一格是 pivot 本身，不用和自己比
  for (let i = left; i < right; i++) {
    if (array[i] < pivotValue) {
      swap(array, i, partitionIndex);
      partitionIndex++; // partitionIndex 往右移動，較小區長大一格
    }
  }

  // 迴圈結束時，partitionIndex 一定是較大區的第一格
  swap(array, right, partitionIndex);

  return partitionIndex;
}

function swap(array, firstIndex, secondIndex) {
  const temp = array[firstIndex];
  array[firstIndex] = array[secondIndex];
  array[secondIndex] = temp;
}

const numbers = [8, 3, 1, 7, 0, 10, 2];
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers); // [0, 1, 2, 3, 7, 8, 10]

quickSort 的 base case 藏在 if (left < right) 這個條件裡。left === right 是這段只剩 1 個元素、left > right 是這段是空的，兩種都不需要做任何事，所以不必另外寫一個 return。

跑完整個遞迴過程

第一次 partition 已經走完了，陣列是 [1, 0, 2, 7, 3, 10, 8]，partitionIndex 是 2。接下來左右兩側各自再做一次：

1. 左側是 index 0 到 1 的 [1, 0]，pivot 是 0。掃描時 1 >= 0，什麼都不做，partitionIndex 停在 0，收尾把 0 和 1 對調，陣列變成 [0, 1, 2, 7, 3, 10, 8]。0 定位在 index 0，它左邊是空的、右邊只剩 index 1 一格，兩邊都到 base case
2. 右側是 index 3 到 6 的 [7, 3, 10, 8]，pivot 是 8。7 和 3 都小於 8，各自和自己對調（i 和 partitionIndex 剛好同一格），partitionIndex 推到 5，10 >= 8 所以不動，收尾把 8 和 10 對調，陣列變成 [0, 1, 2, 7, 3, 8, 10]。8 定位在 index 5
3. 接著處理 8 的左側，也就是 index 3 到 4 的 [7, 3]，pivot 是 3。7 >= 3，partitionIndex 停在 3，收尾把 3 和 7 對調，得到 [0, 1, 2, 3, 7, 8, 10]。8 的右側只剩 index 6 一格，到 base case

排序完成，整趟總共做了 4 次 partition、11 次比較。那這 7 個元素分別是什麼時候定位的呢？每做完一次 partition 就有一個元素永久定位，其中 4 個是這樣定位的，剩下 3 個是在某次遞迴縮到只剩 1 格時自動就位的。

時間複雜度：由分割形狀決定

接著來看看時間複雜度～

單次 partition 是一次線性掃描

先看一次 partition 要多少成本，它就是一個從 left 跑到 right - 1 的迴圈，每一格做一次比較，可能做一次交換，中間沒有巢狀迴圈、也沒有任何一格被走過兩次。因此處理 N 個元素的一段陣列，一次 partition 大約是 N 次比較，成本是 O(N)。

這和 Merge Sort 的 merge 是相同的，兩者都是走過這一段的每個元素一次。真正決定總成本的，是這種線性掃描要做幾次。

最佳與平均 O(N log N)

先看最好的情況，也就是每次挑到的 pivot 都落在正中間，那麼一段 N 個元素會分成兩段各約 N/2，再分成 N/4，一路減半到只剩 1 個，層數就是 log₂N。這和昨天對半切的層數的概念相同，只是 Merge Sort 是照位置切、一定切在正中間，Quick Sort 是照值切、切在哪要看 pivot 挑得好不好。

每一層的工作量呢？同一層雖然有好幾段子陣列，但它們都來自原本那 N 個元素，加起來最多就是 N 格。因此總成本是「每層約 N」乘上「約 log₂N 層」，也就是 O(N log N)。

那平均情況為什麼也算 O(N log N)？因為分割不必對半才有這個結果。就算每次都切成 1 比 3，以比較深的那一側算，層數是以 4/3 為底的對數，換算過去仍然只是 log₂N 乘上一個固定倍數，而 Big O 會把常數倍拿掉。隨機排列的資料裡，pivot 落在極端位置的機率很低，所以平均下來仍然是 O(N log N)。

最壞 O(N²)：Pivot 每次都落在一端

那最壞情況長什麼樣子呢？既然層數是由分割形狀決定的，最糟的形狀就是每次都完全不平衡，也就是 pivot 每次都是這段裡的最大值或最小值。這時候一側是空的、另一側裝著剩下的全部，一次 partition 只讓問題少掉 pivot 那一個元素。

拿已經排好的 [1, 2, 3, 4, 5, 6, 7] 來看，固定挑最後一格，pivot 是 7，是整段最大的，掃完之後沒有任何元素需要換位置，partitionIndex 停在最後一格，左側是 index 0 到 5 的 6 個元素、右側是空的。接下來這 6 個元素的 pivot 是 6，情況一模一樣，如此一路下去。比較次數是 6 + 5 + 4 + 3 + 2 + 1 = 21 次，一般式是 N(N-1)/2，成本退化成 O(N²)。

完全反序的 [7, 6, 5, 4, 3, 2, 1] 同樣是 21 次，只是方向相反，pivot 1 是整段最小的，每次都只有右側留下東西。

圖 4 同樣 7 個元素，平衡的分割只有 3 層，落在一端的分割拉成 6 層

空間複雜度：in-place 不等於 O(1)

省下來的：result 陣列

Merge Sort 的 O(N) 額外空間花在 merge 每次配置的 result，Quick Sort 則沒有這個東西，partition 只在原本的陣列上做 swap，swap 用到的 temp 是一格固定空間，和陣列多長無關，遞迴也只是傳兩個索引下去，不複製任何一段資料。前言想要的那個目標到這裡確實達成了。

沒省掉的：call stack

不過 Quick Sort 的 Auxiliary Space 並不是 O(1)，Day 13 說過遞迴的額外空間通常就是它的最大遞迴深度，而 Quick Sort 每往下一層就多掛一個 frame 在 call stack 上，這部分無法避免。

深度是多少呢？這個深度就是前面算過的層數，答案又回到分割形狀。分割接近平均時，深度是 log₂N，額外空間是 O(log N)，主例的 7 個元素最深就是 3 層；分割每次落在一端時，那條遞迴鏈的長度就是 N，額外空間變成 O(N)，已排序的 7 個元素會變成 6 層深。

也就是說，分割這件事同時決定了兩種成本：分割形狀好，時間是 O(N log N)、空間是 O(log N)；分割形狀壞，時間變 O(N²)、空間變 O(N)。

前面說過 Quick Sort 是原地排序，這裡要注意的是，原地的意思是「不需要一份和輸入等比例的資料副本」，並沒有承諾額外空間是 O(1)，遞迴需要的 call stack 一樣是真實的記憶體成本。

Pivot 怎麼挑，以及和 Merge Sort 的取捨

固定選最後一個的代價

Pivot 固定挑最後一格會怎麼樣呢？其實前面已經看到了：輸入完全排好或完全反序時，pivot 每次都是極端值，直接落進 O(N²)。而這兩種輸入在實務上並不少見，資料剛從資料庫照某個欄位撈出來、或是拿一份已經排好的清單再排一次，都會踩中。這也是 Quick Sort 和 Merge Sort 最大的差別，Merge Sort 的成本只跟陣列長度有關、和裡面的值排成什麼樣完全無關，Quick Sort 的成本則是全部押在 pivot 挑得好不好上面。

常見的改法有兩種，一種是隨機挑一格當 pivot，讓輸入的形狀不再能決定分割形狀，這樣就沒有哪一種特定輸入會穩定觸發最壞情況；另一種是三數取中，拿這段的頭、中、尾三個值，取中間大的那個當 pivot，成本只多兩三次比較，卻能讓已排序的輸入剛好挑到正中間。兩種做法都不改變最壞情況仍是 O(N²) 這件事，改變的是踩到最壞情況的機率。

和 Merge Sort 對照

把昨天那四種輸入拿來各跑一次 Quick Sort，和 Merge Sort 放在一起比較次數：

Merge Sort 那一欄只在 12 和 14 之間，Quick Sort 那一欄從 15 跑到 28，而 28 正好是 8 個元素的 N(N-1)/2，也就是 Day 14 的 Bubble Sort 在最壞情況下的次數。最整齊的那兩種輸入反而花掉最多次比較，這一點和前三個排序都相反。

昨天那張排序演算法比較表補上 Quick Sort 如下：

另外，Quick Sort 的 Best Case 不是「陣列已經排好」。前面四個排序分成兩種：Bubble Sort 和 Insertion Sort 的 Best Case 是已排序的輸入，Selection Sort 和 Merge Sort 則是三種情況都一樣、沒有哪一種輸入特別好；Quick Sort 兩種都不是，它的 Best Case 是每次挑到的 pivot 都落在正中間，而已排序的輸入在固定挑最後一格的寫法下，剛好是 Worst Case。

昨天那個穩定排序 (stable sort) 的性質 Quick Sort 也沒有，原因就在收尾那次交換。merge 每次只從兩段的最前面各取一個，相等時固定取左邊，同分的元素因此永遠不會越過彼此；Quick Sort 的收尾卻是把 pivot 和 partitionIndex 那一格對調，而這兩格可能隔了大半個陣列，被換走的元素等於被整段丟過去，中途跨過誰完全看資料長什麼樣。所以鍵值相同的元素排完之後，相對順序不保證維持原樣。

既然 Quick Sort 的最壞情況比 Merge Sort 差，那什麼時候還會想選它呢？除了額外空間比較省之外，它的常數成本也比較低，全程只在同一個陣列上交換，沒有配置新陣列、也沒有把資料搬進搬出的開銷。Quick Sort 和 Merge Sort 的取捨大致是這樣：需要一個不管拿到什麼輸入，成本都不會超過 O(N log N) 的保證，選 Merge Sort；平均表現和記憶體空間比較重要，且願意用隨機或三數取中來降低 worst case 機率，選 Quick Sort。兩個方法各有好壞，沒有哪一個一定是最好或最快的。

延伸：Quickselect

partition 除了拿來排序，還有一個很好用的用途。先看一個問題：給一個沒排序的陣列，要找出裡面第 4 小的值，會怎麼做呢？

最直覺的做法是先整個排好，再讀 index 3 那一格，用 Quick Sort 的話是 O(N log N)。可是仔細想想，這樣做的工作量遠超過問題需要的，我們只想知道其中一格是什麼，卻把全部 N 個元素都排到定位了。

Quickselect 就是用來省掉多餘那部分的：

Quickselect（快速選擇）用 partition 把 pivot 送到最終位置，再比較目標索引和 partitionIndex，只往可能包含答案的那一側繼續找。

關鍵在 partition 的特性，partition 一結束，partitionIndex 就是 pivot 在完全排好之後的位置。換句話說，只要跑完一次 partition，就順帶知道了 pivot 是第幾小的元素，不必多做任何事。這時候和目標索引比較，只有三種情況：

• 目標索引小於 partitionIndex：答案一定在左側，右側和 pivot 都可以整個丟掉
• 目標索引大於 partitionIndex：答案一定在右側，左側和 pivot 都可以整個丟掉
• 兩者相等：pivot 就是答案，直接回傳

以 [8, 3, 1, 7, 0, 10, 2] 為例，假設要找第 4 小的值（也就是 index 3），流程如下：

1. 第一次 partition 和排序時完全一樣，得到 [1, 0, 2, 7, 3, 10, 8]、partitionIndex 是 2。目標索引 3 大於 2，答案在右側，index 0 到 2 那三格連同 pivot 一起排除，接下來只處理 index 3 到 6
2. 對 index 3 到 6 這段做 partition，pivot 是 8，得到 [1, 0, 2, 7, 3, 8, 10]、partitionIndex 是 5。目標索引 3 小於 5，所以往左，只處理 index 3 到 4
3. 再做一次 partition，pivot 是 3，得到 [1, 0, 2, 3, 7, 8, 10]、partitionIndex 是 3，和目標索引相等，答案就是 3

寫成程式如下：

function quickSelect(array, left, right, targetIndex) {
  const partitionIndex = partition(array, left, right);

  // pivot 剛好落在目標位置，它就是答案
  if (targetIndex === partitionIndex) return array[targetIndex];

  // 只往可能有答案的那一側繼續，另一側整個丟掉
  return targetIndex < partitionIndex
    ? quickSelect(array, left, partitionIndex - 1, targetIndex)
    : quickSelect(array, partitionIndex + 1, right, targetIndex);
}

const values = [8, 3, 1, 7, 0, 10, 2];
console.log(quickSelect(values, 0, values.length - 1, 3)); // 3

和 quickSort 相比，quickSort 兩側都遞迴，quickSelect 只挑一側。

圖 5 Quickselect：每一輪丟掉一整側

整趟只做了 3 次 partition，而且處理範圍從 7 格縮到 4 格再縮到 2 格。這結構很像 Binary Search，每一輪都丟掉一整側，差別在 Binary Search 靠的是陣列本來就排好，Quickselect 靠的是 partition 做出來的那個分界。

成本上，Quick Sort 每一層要處理的元素總數都是 N，因為兩側都得繼續；Quickselect 只走一側，範圍平均每輪減半，總工作量是 N + N/2 + N/4 + …，平均是 O(N)。最壞情況仍然是 O(N²)，理由和 Quick Sort 一樣，pivot 每次都落在一端時範圍只縮小一格。也就是說，同一個 partition，遞迴兩側是排序，只遞迴一側就是選第 k 小的值。

小結

小小總結一下今天對 Quick Sort 的認識～

• 為什麼需要 Quick Sort？ 因為 Merge Sort 那個 O(N) 的額外空間是合併造成的，而合併之所以必要，是因為對半切出來的兩段之間沒有大小關係。Quick Sort 改成照值分割，讓左側每一個都小於右側每一個，兩側排好就直接接得起來，合併那一步就不需新陣列空間。
• 用了 Quick Sort 之後差在哪？ 差在節省了空間，但也犧牲了 Worst Case 的保證。它全程在同一個陣列上交換，額外空間只剩 call stack；但成本變成由 pivot 挑得好不好決定，分割接近平均時，時間是 O(N log N)、空間是 O(log N)；pivot 每次落在一端時，時間變 O(N²)、空間變 O(N)。
• Quick Sort 到底是什麼？ 它挑一個 pivot，用一次線性掃描把比 pivot 小的元素換到左側，再把 pivot 換到兩區的交界處，讓 pivot 落在最終位置，接著對左右兩側遞迴做同樣的事。排序發生在分割那一步，它的效率取決於分割出來的形狀。

實際使用時，還可以記住幾件事～

• Quick Sort 是原地排序，但額外空間不是 O(1)，遞迴的 call stack 也要算，且它同樣由分割形狀決定
• Quick Sort 的 Best Case 是 pivot 每次落在正中間，不是輸入已經排好

圖表說明：本文圖表由作者整理，並使用 Claude Code 協助繪製；內容與數據由作者確認。

Reference

• Master the Coding Interview: Data Structures + Algorithms
• 《A Common-Sense Guide to Data Structures and Algorithms, Second Edition》
• Wikipedia：Quicksort
• Wikipedia：Quickselect
• Sorting Algorithms Animations