同學提問：執行下面的程式碼
let arr = [1, 3, 2]
arr.sort((a, b) => {
console.log(`Now comparing a = ${a} & b = ${b}`);
return a - b;
});得到結果會是
Now comparing a = 3 & b = 1
Now comparing a = 2 & b = 3
Now comparing a = 2 & b = 3
Now comparing a = 2 & b = 1為什麼其中的 2 和 3 會被比較兩次呢？
在 Array.sort() 裡面放入 console.log() 還真是我沒有想過的點子，非常有趣，但一放進去就發現問題，讓我花了半天的時間尋找答案。那麼同樣的，接下來就歡迎有興趣的朋友跟著我一起探索吧！
先講結論
根據經驗，大概有 70% 以上的人不會把文章看完，所以這裡先講結論
在目前的 V8 engine 當中，處理 array.prototype.sort() 的時候是使用 Timsort（跟我同名的）排序法。
Timsort 的概念是，將一大筆資料拆成小批次的資料，在小批次的資料當中使用 Binary Inserttion Sort，之後再將已經排序好的小批次資料，用 Merge Sort 把所有小批次資料整合在一起。
不過在進行 Binary Insertion Sort 之前，Timsort 會進行一個特別的動作，就是它會先去搜尋「小批次資料當中前面的『有序』資料」，把這些資料抓出來之後，這段資料就不需要進行 Binary Insertion Sort。
因此剛剛的結果，其實是 console.log 分別在不同的階段被呼叫（因為資料量小，所以沒有動用到 Merge）：
Now comparing a = 3 & b = 1 // 尋找有序資料 (nature run)
Now comparing a = 2 & b = 3 // 尋找有序資料 (nature run)
Now comparing a = 2 & b = 3 // Binary Insertion Sort
Now comparing a = 2 & b = 1 // Binary Insertion SortStart from Array.prototype.sort()
在 MDN 的說明，我們在使用 array.sort() 的時候，可以傳入一個 compare function：
arr.sort([compareFunction])根據定義，如果沒有傳入 compareFunction，那麼它就會自動將陣列當中的 elements 轉成字串，並依照 UTF-16 code units order 排序。這也就是為什麼 “80” 會排在 “9” 的前面。
如果有傳入 compareFunction，那麼 compareFunction 就會依照 timsort 演算法抓取兩個 elements 進行比較，然後回傳結果。case 如下：
- 如果 compareFunction(a, b) 回傳 0，那麼 a 排在 b 前面
- 如果 compareFunction(a, b) 回傳大於 0 的值，那麼 b 排在 a 前面
- 如果 compareFunction(a, b) 回傳小於 0 的值 ，那麼 a 排在 b 前面
所以通常如果想要遞增排序，會將回傳值設定為 a-b，這樣一來，如果前面的 a 小於後面的 b，那麼 a 減 b 就會是小於 0 的值，根據上面的規則，a 就會排在 b 的前面，整個陣列也就會是遞增排序。
arr.sort((a, b) => {
return a - b;
});反之如果要遞減排序，那麼就只要將回傳值改成 b-a
看到這裡，其實就會發現我們可以在 compareFunction 裡面做任何事情，然後配合剛剛提到的規則來影響最後排序結果。當然我們也可以在 compareFunction 裡面放入 console.log 來看看演算法是如何實際抓取 elements 來進行比較。
但是看到這裡，並沒有辦法回答我們的問題，而且我們也沒有實際看到 Timsort。依照過去的經驗，如果我們想要了解一個套件是如何運作，可以查看他的原始碼，在使用 Node.js 開發的情況下，套件也通常都是由 JavaScript 所寫成。不過，如果我們想要知道 JavaScript 本身是怎麼運作的，那我們又應該去哪裡找他的原始碼呢？
V8 — a JavaScript engine
在 Chrome browser 或是 Node.js 的環境下，JavaScript 程式碼仰賴 V8 engine 進行編譯，然後才能被執行。在不同的環境下會有不同的 JavaScript engines，而不同的 engines 所執行的 JavaScript 雖然都符合 ECMAscript 的規範，但在細節上可能還是會有所不同，譬如 Array.prototype.sort() 所採用的演算法。
因此這篇文章談的是 “How Array.prototype.sort() works in V8”，如果是在不同的 JavaScript engine 上，結果可能就會不同。
所以如果要知道 Array.prototype.sort() 實際上是怎麼運作的，那麼就不得不去看一下 V8 engine。
Getting things sorted in V8
Getting things sorted in V8 這篇文章提到 Array.prototype.sort() 是如何被實現的，我得承認我沒有完全看懂，不過有以下幾個 takeaways
- V8 原本是使用 Quick Sort 和 Insertion Sort 演算法來處理，不過目前改用 Timsort
- 實際執行 sorting 之前，V8 會針對 array 進行前處理（不同的 engine 會有不同的處理結果）
- V8 引入了 torque 這個新的程式語言
- Timsort 不是遞迴執行的 (it works iteratively)
- Timsort 會從 array 由左到右建立 “runs”，也就是在整個資料中先取出小批次資料進行處理
- Nature run 是指在排序前「已經有序」的資料
- 每次執行一個 “run” 的時候，如果有非 nature run 的資料，那麼就會使用 Binary Insertion Sort 讓整個 run 有序
- 在一些 runs 完成排序之後，就會開始逐步將部份 runs 整合成一筆有序的資料。最後的結果是，所有的 runs 將被整合成一個 sorted array 並回傳
看完這些，對於 V8 如何處理 sorting 有個概念，但還是不知道為什麼 2 & 3 要被比較兩次。於是，就毅然決然地跳入 V8 engine 的原始碼去看
V8 engine source code
我們可以在 這裡 看到 V8 處理 array sorting 的程式碼。會發現這裡的程式碼灰色一片，應該是編輯器還沒有支援 torque 這個語言。
在這裡我們不會看完所有 functions， 如果直接來到檔案的最下面，可以看到 ArrayPrototypeSort 主要呼叫 ArrayTimSort() 來執行任務
transitioning javascript builtin
ArrayPrototypeSort(...){
...
ArrayTimSort(context, sortState);
...
}在 ArrayTimSort() 當中，看起來主要執行排序任務的是 ArrayTimSortImp()
transitioning builtin
ArrayTimSort(...){
...
ArrayTimSortImpl(context, sortState, numberOfNonUndefined);
...
}因為當初問題本身的資料量算少，這裡我們就重點來看 Timsort 當中的 Binary Insertion Sort 的運作，其他關於 Merge 的部分就大膽的暫時跳過。
這次主要看以下四個 functions:
以下依照程式執行的流程說明 functions 之間的內容，為了方便，就容我用條列式的方式說明。
另外，也假設我們目前在執行下面這段程式碼，其中目標陣列為 [1, 3, 2]
let arr = [1, 3, 2]
arr.sort((a, b) => {
return a - b;
});Stage 1: ArrayTimSortImpl()
- L2: length 是資料陣列的長度。
- L4: 宣告變數
remaining為陣列長度，也就是 3 - L9: 宣告變數
low為 0 - L10: 要找到 Timsort 當中 run 的最小執行長度，因此呼叫
ComputeMinRunLength()function，並傳入remaining，這個值目前為陣列總長度 3
Stage 2: ComputMinRunLength()
- L12: 宣告變數
n為傳入的參數nArg，也就是剛剛傳入的陣列長度 3 - L13: 宣告變數
r為 0 - L16: 如果
nArg(陣列長度) 超過 64，就一路除以 2。其中 r 的設計是，如果n大於且為 2 的次方，那麼最後執行完 while 迴圈r的值為 0；若不為 2 的次方，那麼就是 1。不過在這裡因為陣列長度太小，根本不會執行 while 迴圈，n仍然為 3、r為 0 - L21: 宣告變數（也是最後的回傳值）
minRunLength為 3
Stage 3: ArrayTimSortImpl()
- L10: 於是，
minRunLength的值為 3 - L12: 要計算先前提到的「已經存在的有序資料」，呼叫
CountAndMakeRun()function，傳入的參數值分別為 0, 3
Stage 4: CountAndMakeRun()
這裡主要的任務是去找「已經存在的有序資料」也就是 nature run
- L23: 引入目標陣列，也就是
[1, 3, 2]作為workArray - L25: 宣告變數
low，也就是傳入的第一個參數 low + 1，也就是 1 - L26: 此時
high是傳入的第二個參數，也就是 3，和low不相等，因此不會執行 - L28: 宣告變數
runLength為 2 - L30: 宣告變數
elementLow為workArray[1]，其值為 3 - L31: 宣告變數
elementLowPre為workArray[0]，其值為 1 - L32: 呼叫 compareFunction 出場，由於原本的 arr.sort() 裡面只有 return a-b，所以這裡的 compareFunction 回傳結果是 2。變數
order為 2 。特別注意的是，這裡是第一次 compareFunction 被呼叫的地方 (1 & 3)，因此 compareFunction 當中的 console.log 會被呼叫 - L37: nature run 的狀態判斷，因為
order為 2，因此isDescending為 false，代表透過前兩個 elements 判斷，接下來要找的 nature run 會是個遞增排序的資料。 - L39: 宣告變數
previousElement，其值為 3 - L41: 宣告變數
currentElement，由於idx為low+ 1，值為 2，因此currentElement也就是workArray[2]，值為 2 - L42: 判斷
currentElement與previousElement之間的order，這裡的order為 2 – 3= -1。這裡是第二次 compareFunction & console.log 被呼叫的地方 (2 & 3) - L44: 負責判斷是否要繼續往前找 nature run。由於目前
isDescending為 false，且order小於 0，因此會執行 break，跳出 for loop。因此，目前找到的 nature run 為 [1, 3] - L45: 如果找到的 nature run 是反序的，譬如 [3, 1]，那麼就會直接反轉變成正序（備註：這裡的正反序是根據 compareFunction 而定，如果當中改成 return b-a，那麼上面的結果都會反過來）
- L58: 回傳
runLength，值為 2
Stage 5: ArrayTimSortImpl()
中場整理一下，關於目前有的變數值
low為 0minRunLength為 3currentRunLength為 2remaining為 3
接下來繼續來看程式碼
- L17:
forcedRunLength為minRunLength或remaining之間的最小值。不過因為兩者都為 3，因此forcedRunLength為 3 - L18: 終於，要進入了 BinaryInsertionSort()，這裡傳入的參數值分別為 0, 2, 3
Stage 6: BinaryInsertionSort()
這裡其實就是執行 Binary Insertion Sort，如果對於這個排序方法還不是很理解，可以觀看這個影片的說明。
這裡先幫大家整理一下變數：
- 傳入的參數
low,startArg,high分別為 0, 2, 3 (承接上一步) start為startArg，值為 2left為 0right為start2pivot為workArray[right]也就是 2mid為 0 + ( (2 - 0 ) >> 1)，也就是 1
接下來，就可以開始跑 Binary Insertion Sort。以下為 Binary Insertion Sort 分解步驟的示意圖：
Step 1: 拿 pivot 和 workArray[min] 比較，得到結果 order 為 -1，因此 right 的值變為 1。這裡是第三次 compareFunction & console.log 被呼叫的地方 (2 & 3)
Step 2: 由於此時 left < right，while loop 會繼續執行。重新計算 mid 的值為 0
Step 3: 拿 pivot 和 workArray[min] 比較，得到結果 order 為 1，因此 right 的值變為 1。這裡是第四次 compareFunction & console.log 被呼叫的地方 (1 & 2)。另外，
Step 4: left 值變為 mid + 1
Step 5: 此時left 等於 right，while loop 停止執行。往下執行 array element 的位移。只移動 left 右邊的部分
Step 6: 執行 workArray.objects[left] = pivot; 完成排序
在以上的過程中，可以很清楚看到 compareFunction 在哪裡被呼叫：前兩次在 CountAndMakeRun() 當中，後兩次在 BinaryInsertionSort() 當中，也就是
Now comparing a = 3 & b = 1 // CountAndMakeRun()
Now comparing a = 2 & b = 3 // CountAndMakeRun()
Now comparing a = 2 & b = 3 // BinaryInsertionSort()
Now comparing a = 2 & b = 1 // BinaryInsertionSort()也就很清楚的解答了「為什麼 2 和 3 會被比較兩次」
雖然花了不少時間進行這段探索，但其實也只摸到了Array.prototype.sort 當中小小的一塊，還有一半以上的原始碼沒有機會可以看到。不過越深入走進原始碼，越能夠找到意想不到的答案。
About me
Self-taught and trained in software development knowledge and skills, I am passionate about creating changes through technology.
Find more at Github, LinkedIn, Teaching at ALPHA Camp
