這一講的是一群元素中，不用排序找出第幾大的問題。
一開始講的是同時找最大最小，需要花得比較次數，直覺想是 2n-3 次，但其實只要 floor(3n/2)-2 次即可。9.1 利用狀態機 model了 Min-max problem 的lower bound。 p4~p10.
這個問題是選i小的問題，不用用到 nlog(n)的時間。基本上是學 quicksort 的 pivot 比較大小，不過 pivot 要小心的挑 。
9.3 就是講如何小心的挑，
先五個五個做 insertion sort，再找中位數，這是一個經典的演算法。
一般 sort 都是以比較為基礎來討論的，首先討論的是 comparison-based 的演算法 worst case 的下限。
基本的觀念是建立一個 decision-tree model 來對應各種排序演算法。接下來再證明在 worst case 下至少要花Ω(nlgn) 的時間。 p3.~p.4
有了 lower bounds，接下來討論一些演算法是否符合需求， merge sort、Heap sort 符合需求 (quicksort worst case 是ο( n2))。 heap sort 因為 heapify 要跟左右子節點比較，所以會比 merge sort 比較的次數多。
那麼 merge sort 的比較次數是不是最佳的呢? NO
接下來老師就補充，merge sort 和最佳次數的關西。 p.6 ~ p. 9
注意 p.8 用圖示簡單的示範了 5 個元素時的 "merge insertion sort" 演算法，個元素的插入順序很重要。
接下來討論到不是用比較為基礎的排序，老師一開始討論說 Radix 其實太輕忽了，其實實數、字串等也可以用 Radix 比較， Radix sort 的缺點是占空間，但效率很好。目前 C++ Library 的排序演算法是 IntroSort (quicksort 的改良版)。
Counting Sort 有個重要概念、Stable，要達到 Stable 那麼輔助陣列要累加。
Radix 有分成 LSD & MSD 、LSD 比較實用，但兩個複雜度相同，用 LSD 時也就需要 stable counting sort。 p.15 利用數學歸納法證明了 LSD Radix 的正確性，基本上就 1...i 位數都排序，那麼 在討論 i+1 位數是否有排序。
分析了一下 LSD Radix Sort 有個很重要的觀念是如何切割....
p.17 有說明如何切割最好: r = lgn 時
當 r 比 lgn 大或小時效能都不會好。
p.18 說明為什麼Radix會比較快，排序所花的時間主要是"看"的次數。 舉個例子: 考慮 16-bit 的整數有 216 個。Radix 只要看4次，而MergeSort要看16次。
這裡也做了一些假設，只排 unsigned integer，若是要比較 signed integer、string、real 也是可以，但要多做一些步驟。
p. 19 ~20 比較 signed integer (最後一部分相加在排)
p. 21 ~22 比較 string (用了 weighted index)
最後談到的是 Bucket Sort 有點 Hash Table 的概念。 這裡做了些機率分布的假設，假設平均分布。那 expected running time 為 θ(n)。
p.26 做了簡單的 Correctness 證明
p.27 做了大略的分析
p.28 ~ p.33 做了詳細的證明
