演算法中最常提到可以在 Average Case 內把複雜度壓在 n log(n) 下的有三種排序演算法，簡單回顧一下這三種排序演算法的原理：
- Merge Sort：先拆分至長度為 1 後再逐步融合，利用把兩個已排序好的陣列合二為一只需要 O(n) 的特性
- Quick Sort：選出基準(Pivot)後把比基準值小的資料放左邊、比基準值大的資料放右邊，基準值則置於兩者中間 (Partition)，再對基準值左右的資料集繼續往下做 Quick Sort
- Heap Sort：首先建立最大堆疊，接著取出數列中的最大值(根節點)，利用最大堆疊每次取出最大值只需要 O(logn) 的特性，依序取出最大值
雖然 Merge Sort、Heap Sort、Quick Sort 三者在 Average Case 的複雜度一樣，但實際做排序實驗看看彼此需要的時間，下圖是排序一百萬筆資料1000次的時間分布：
結果出來：Quick Sort > Merge Sort > Heap Sort
Quick Sort 不愧其名地拿下大資料組的冠軍。當然實際排序還需要考量到 Quick Sort 是不穩定排序，而 Merge Sort 需要額外 O(n) 記憶體空間。
另外，也可以看出雖然三者的時間複雜度相同，但執行時還必須考量到 Compare、Swap、Recursion 的次數與情形，導致其速度上可以差到兩到三倍之多，因此實務上時間複雜度並不是唯一考量。
但 Quick Sort 的問題是：如何避免 Quick Sort 選到不適當的 Pivot (陣列中的最大或最小值) 導致落入 O(n²) 的困境？
「Niklaus Wirth 提出從第一個、中間、最後一個三個數中取出中位數當作基準，但經過設計的破解序列仍能大幅降低此演算法的效能。因此就有攻擊者精心設計序列傳送到伺服器來進行阻斷服務（DoS）攻擊。」[Wikipedia]
為了避免這種特殊狀況出現，在進行 Quick Sort 時必須同時監測遞迴的深度，如果深度 > log(n)，那就改採 Heap Sort 或 Merge Sort 來應對。
至於遞迴深度超過後， Heap Sort 或 Merge Sort 該選誰？
根據剛剛的實驗，Merge Sort 速度上會勝過 Heap Sort ，但 Merge Sort 有個最大的問題：需要 O(3n) 的記憶體空間(Ref)。
雖然在大部分狀況下記憶體空間並不是難事，但如果資料達到數 GB 之多，Merge Sort 便需要保留 Heap Sort 三倍的記憶體空間，如果因記憶體不足而進到 Swap ，那會直接導致速度崩潰或甚至無法執行。
因此在空間與時間的平衡下選擇 Heap Sort。
最後，雖然平常我們討論的幾乎都是大資料的情形，但上述這些排序演算法本質上都是分治法(Divide and Conquer)，也就是不斷拆分下去，最後都會把資料縮減到一定程度。
那問題就來了：對於小資料而言，有比 Quick Sort 更快的演算法嗎？
是的，有，它就是 Insertion Sort。讓我們比較小規模資料(20筆)下的排序速度，下圖是排序20筆資料10萬次的時間分布：
可以發現：Insertion Sort > Quick Sort > Merge Sort ~ Heap Sort
小規模資料下，換成是 Insertion Sort 逆轉勝拿下冠軍！
所以，根據上面一步步推導的結果，C++ STL 中所用的排序法便是所謂的內觀排序(introsort)，步驟如下：
- 原則上採取 Quick sort
- 監控遞迴的深度，太深(>log(n)) 時改採 Heap sort
- 長度下降到一定程度(20筆)，採用 Insertion sort
- 本文的 log(n) 皆代表 log_2(n)
Source Code，演算法相關的程式碼取自 GeeksforGeeks。
工商服務
這是我開的粉專，覺得有幫助的話可以幫我點個讚，另外我在台大訓練班也有開演算法課程，參考書目是我自己寫的演算法生存指南，有興趣的話可以賞個光。
粉專連結：http://bit.ly/3evM7pk
台大訓練班：https://bit.ly/3mK54c0
演算法生存指南：bit.ly/3HHlTkb
