上一章，書中介紹了資料結構中的“Hello World”——二叉搜尋樹，這一章介紹排序演算法中的“Hello World”——插入排序。作者選用插入排序是因為它比較直觀，但是在效能上不如一些分而治之的排序策略如：快速排序和歸併排序，所以在現實應用中不會將插入排序作為一種通用的排序演算法。這一章是分析它的效能問題並逐步解決它。
插入排序的思路：將一個序列分為兩個部分，分別為已排序部分與未排序部分。不斷的將未排序部分的元素取出插入到已排序部分。
插入
我們是怎麼將未排序的元素插入到已排序部分的元素中的？將元素取出後我們從已排序部分的元素從左往右找到手頭元素的位置插入。
改進一：二分查詢
上邊這種插入方式感官上沒有那麼智慧，人在處理撲克牌的時候感官上就變得智慧多了。類似於查詢中的二分查詢，我們也可以透過二分查詢先找到目標元素所需要插入的位置，這樣子插入部分的效率會提高一些。
改進二：使用連結串列
插入時候如果是使用陣列可能存在需要挪動大量元素的情況，若使用連結串列的方式進行替換，可以節省大量的移動時間。面對實際情況我們可以考慮是否使用這種做法。
改進三：使用二叉搜尋樹進行最終的改進
我們似乎進入了死衚衕：必須同時提高查詢的速度與插入的速度，單獨提高一種，仍然是O（n^2）的時間複雜度。
使用二分查詢是唯一能把比較次數降低到O（lgn）的方法。另外，必須改變資料結構，我們不能在普通資料結構中實現常數時間插入。
二叉搜尋樹本身就被定義為支援二分查詢。同時一旦找到了插入位置，我們可以在常數時間插入一個新節點。透過這種方式我們得到最終的排序結果是一顆二叉搜尋樹。結果序列我們進行一箇中序遍歷就可以得到了？透過這種方式進化到樹排序。
