# C++ sort 原理

## 前言
禮拜四上課時討論到不同程式語言的sort()底層原理，這邊我對C++ 的部分比較感興趣；我剛好趁有空時翻一下原始碼，略為理解C++ sort() 的架構，並分享給大家。本篇會著重在我較為熟悉的**取中位數**與**呼叫insertion sort** 的部分，剩餘漏掉的部分歡迎電神們補充~

**先說結論**，大致上C++ sort()在元素個數大於16的情況下會使用類似quick_sort()的操作，若quick_sort()遞迴深度過深，則採用partial_sort()，元素個數小於等於16時，則使用insertion_sort()

後記:原本想說2小時搞定，結果陸陸續續打了快六個小時...

## 原始碼位置
被我從MinGW中找到了，版本是6.3.0，有興趣的可以去看看

## 原理
### 一切的開始
就我目前的理解而言，平常呼叫的C++ sort() 是在這裡定義的

還有這裡

兩者主要的差別是參數的數量，有用過sort() 的人應該知道，第三個cmp function參數可傳可不傳，而底層的程式碼則正是利用了C++ 的Overloading特性達成的

sort() 會呼叫 __sort()

### __sort()
被sort()所呼叫

定義在此

__sort() 會呼叫 __introsort_loop() 跟 __final_insertion_sort()

### __introsort_loop()
被__sort()所呼叫

定義在此

不難看出這是一個遞迴的函式，且遞迴越多次，__depth_limit參數就會越來越小。

while (__last - __first > int(_S_threshold)) 這個條件是在說，如果代表目前quick sort 操作範圍的那兩個指標(__last,__first)間涵蓋的元素夠多，就繼續迴圈；否則就交給insertion sort() 解決。
-> _S_threshold就是區分quick sort 與insertion sort的邊界

在迴圈中，__depth_limit參數終於用上了，C++設計者為了避免遞迴太多層記憶體會爆掉之類的，設定了一個遞迴次數上限，一旦超過這個上限，就改用__partial_sort() 完成排序的動作；(__partial_sort()我不熟，所以這個就留給電神教我了)
如果還沒超過這個上限，就執行
1. 呼叫__unguarded_partition_pivot()取得__cut參數
2. 呼叫自己，可以看到下一輪中的__first參數就是__cut

### __unguarded_partition_pivot()
被__introsort_loop()所呼叫

定義在此

會呼叫__move_median_to_first()，並在最後回傳__unguarded_partition()

### __move_median_to_first()
被__unguarded_partition_pivot() 所呼叫

定義在此

終於被我找到了，原來C++ sort() 真的會取中位數，而且是從**開頭、中間、結尾**各取樣一個數字，接著基於__comp (自定義的比較函式) 將中位數移到第一個位置，函式名取得真好

### __unguarded_partition()
被__unguarded_partition_pivot() 所呼叫

定義在此

這邊跟上課講的quick sort實作方式不太一樣，比較像是把**比pivot小的部分**丟到左邊，剩下的丟到右邊，並回傳中間那個大斷層的位置當作下一次遞迴的__first(也就是__introsort_loop()函式中的__cut)

這樣就能理解這張圖的意思了，就算每次都抓三個數再取中位數，還是不能剛剛好取到中間那個，所以斷層長短不一

因為整段程式碼是在遞迴中進行的，所以會一直切下去，直到該段的長度小於_S_threshold

### __final_insertion_sort()
被__sort()所呼叫，用來收尾那些讓強迫症抓狂的小鋸齒

定義在此

if (__last - __first > int(_S_threshold))的意思是說，如果需要insertion_sort 的元素太多，會依照_S_threshold 分成兩邊進行
-> 分別呼叫__insertion_sort() 跟__unguarded_insertion_sort()

否則，就直接呼叫__insertion_sort()就好

### __insertion_sort()
被__final_insertion_sort()所呼叫

定義在此

類似一般的insertion sort，但分成兩種case
1. 當__i比第一個元素小時，會呼叫_GLIBCXX_MOVE_BACKWARD3()函式將__i插入到第一個位置(可能比較快，或是處理worst case?)
2. 反之，則呼叫__unguarded_linear_insert()函式

### __unguarded_linear_insert()
被__insertion_sort()所呼叫

定義在此
負責將選中的元素插入至正確位置

### __unguarded_insertion_sort()
被__final_insertion_sort()所呼叫

定義在此

可以看到這邊用for迴圈連續呼叫__unguarded_linear_insert()來插入元素至正確的位置