本文為清華大學開放式課程上課心得整理。
Heap Sort
先整理名詞定義與操作方法：
・Max Heap：又稱為 Priority Queue，指的是一棵樹（max/min tree）在有 children 的狀況下， 其任意節點的 key/value 不會比 children 小／大，且一定是一個 complete binary tree。
Max Heap 由於是一個 complete binary tree，因此適合用之前介紹過的 Array Representation 來表示：
Max Heap 插入元素的執行步驟如下：
1. 先確認是否為 complete binary tree
2. 插入新節點
3. 檢查新節點與 parent 的大小是否符合規則，若否則調整節點順序直到符合規則為止Max Heap 刪除元素的執行步驟如下：
1. 刪除 root
2. 將最後的節點搬到 root，再與 children 比較，與最大的 child node 交換位置，持續比較直到符合規則Heap Sort 運用 Max Heap 的資料結構，好處是 insertion 與 deletion 的處理速度會很快；由於在插入與刪除時順序會調換，所以 Heap Sort 不是 Stable Sort。
Sorting on Several Keys
有時候排序不會只針對單一的 key/value 操作，可能會同時針對好幾個 key 做比較，這裡要來討論這種情況下該如何排序。
一個經過排序的 list，有 k1 到 kr 個 key，重要性由 k1 依序往下遞減，當 list 中的 元素 i 排在 j 前面時，即可判定 i 的 key 權重小於 k 的 key，key 的大小定義說明如下圖：
常見的排序方法如下：
・Most-significant-digit（MSD）sort：先根據第一重要的 key 把資料分成若干堆，再依序於每個子集合中根據其他 key 做排序，完成之後 merge。
・Least-significant-digit（LSD）sort：與 MSD 相反，LSD 是先從權重較小的 key 開始分類，再將分類好的堆疊依序組合，再使用次一權重的 key 做分類並做排序，最後再將結果 merge 再一起。
・Bin Sort（Bucket Sort）：如果資料是來自於某些特定的結果（例如撲克牌的四種花色、骰子的點數），假設有 m 種結果，就針對這 m 種結果做出 m 個 buckets，針對條件將元素依序分進 bucket 中，最後再整合。這種方法適用於需要排序的元素數量不大時，如果數量過於龐大，就會比較沒有效率。
・Radix Sort：根據 Bucket Sort 可以再衍伸出 Radix Sort 這種排序方法，radix 指的是底數，根據底數來創建 bucket（假設 radix 是 r，bucket 則為 0~r−1），可以搭配 MSD 或 LSD 做 bin sort；這種方法適用於需要排序的物件數量非常多的時候。
Internal Sorting 總覽
所謂的 internal sorting，指的是在排序的時候，所有的資料都可以存放在記憶體中完成，不需要寫進硬碟，原則上前面所介紹的幾個方法都是 internal sorting，時間複雜度如下圖：
以平均來看，quick sort 的表現會最好；在目標數量很小、特別是有部分目標已經排序好的時候，insertion sort 的效率最好；merge sort 的速度會比 heap sort 快一點，不過由於需要產生額外的 link，因此會多佔用一點儲存空間。因此，我們可以使用混合的方式，針對對象產生適合的排序方法，以達到最好的效能。以 C++ 排序為例：
External Sort
當需要排序的資料量太大、無法在記憶體中儲存，這時就會將 list 寫入硬碟中做後續處理，這種做法便稱為 External Sort。External Sort 每次只會讀其中一部分的資料，針對這些資料做排序，完成之後再寫回硬碟，重複執行直到處理完成，因此需要針對資料做切段，這些切段的區塊稱為 Block。
由於前面提到的 insertion sort、heap sort、quick sort 都需要在記憶體中處理資料，不適用於 external sort，所以只有 merge sort 能使用，由於 merge sort 可以在最後只讀取每個排列好的片段的 leading records 加以組合，節省記憶體用量，是 merge sort 一個很大的優勢。
實際在執行 merge sort 的時候，由於每個 block 的大小不盡相同，如何安排執行緒以達到最大效益也是一個重要的問題；這裡介紹 Optimal Merge of Runs：
從上方結果可以看出，比較大的資料就不適合放在樹比較深的位置。
Optimal Merge Tree
介紹 Optimal Merge Tree 之前，要先討論另一個類似問題：Message Encoding，假設有一串 message m1 到 mi，要如何用最小的 binary 去 encode 這串訊息？這有幾種編碼方式：
這裡介紹 Huffman Code：根據 message 產生一個 binary tree，稱為 decode tree，用來 encode message。
message 的 decoding cost 會與文字 encode 的 bit 數有關，這與前述資料大小有相似的解決邏輯，因此可以在這裡借用該演算法處理：
自主學習：
