[JavaScript] 從 Array 的 sort 方法，聊到各瀏覽器的實作，沒想到 Chrome 和FireFox 的排序如此不同
Array 的原型上有一個非常容易誤用的方法 — sort() ，它總是能讓諸多 JavaScript 新手感到相當地困惑，本篇文章會先介紹 sort 方法的正確使用姿勢，而後討論各家廠商是如何來實作排序。最後再來探討為什麼 sort 常常成為 JavaScript 被抨擊的原因。
目錄
- 前言
- sort 的用法
- 各家實作不一
- 為什麼多數人抨擊 sort
- 寫在最後
前言
JavaScript 的函數用法，總是跟你想的不一樣。這也是我撰寫這篇文章的主要原因之一，常見的 sort 方法太過容易被誤用，導致不斷有人製作成 meme 圖來攻擊 JavaScript 很瞎 (weird)。
另外這篇文章並非教學文 — 雖然還是會介紹語法，但我主要想討論的是「正確的語法」、「實際上的排序實作」、「為什麼它讓人討厭」等等。
sort() 的用法
arr.sort([compareFunction])可以發現 Array 上的 sort 方法是可以接受一個回調函數，MDN 把它稱為compareFunction，我們來看看實際上這個回調函數是怎麼樣去設計的。
function compare(a, b) {
if (在某排序標準下 a 小於 b) {
return -1;
}
if (在某排序標準下 a 大於 b) {
return 1;
}
// a 必須等於 b
return 0;
}我們先不管排序標準，當我們要看懂一個函數的時候，有一件最重要的事，就是看懂傳入的參數代表什麼。於是我們來做一個實驗來看看參數到底是什麼：
Chrome：
FireFox：
靠北，印出來的參數相反！
這個時候你只想比起中指，然後在註解留下：「 gan 你妹夫」。
沒有啦，本來 JavaScript 就沒有規範 compareFunction 傳入的參數到底該是陣列的什麼順序（這跟等等提到的算法有關），compareFunction 只是在制定一個兩數之間的比較規則。
什麼是明確規則？
如果今天要比較的兩個數字分別是 113、114 好了，我們要告訴 JS 的引擎，到底排序的方式是怎樣，這個時候只有三種狀況：a排在b前面、a排在b後面、ab位置不動。
if (a < b) {
return -1;
}
// 如果有兩數 a b
// 當 a 小於 b 的時候
// 幫我把 a 排在 b 前面
if (a > b) {
return 1;
}
// 如果有兩數 a b
// 當 a 大於 b 的時候
// 幫我把 a 排在 b 的後面// a 此時等於 b
return 0;
// 回傳零代表不改變彼此之間的順序
在這個明確規則的定義後，不管 a 跟 b 兩數傳進來的順序為何，我們只在乎它們彼此的排序關係。這也解釋了為什麼同樣的 compareFunction 下，儘管 Chrome 與 Firefox 在接受的參數不一樣，還是能排序出一樣的結果。
再次注意！Compare Function 的這個回調只在乎排序兩數之間的規則。
你可能會覺得有點懵，明明傳進來的順序就不一樣，為什麼可以這樣做，這有點像是在繞口令：
我比你高，換句話說你比我矮，只要規定高矮之間誰在前面、誰在後面就好。
來看看Chrome的輸出會是：
目前正在比較 a = 3 與 b = 1
因為3>1，所以3在1後面
目前正在比較 a = 2 與 b = 3
因為2<3，所以2在3前面
目前正在比較 a = 2 與 b = 3
因為2<3，所以2在3前面
目前正在比較 a = 2 與 b = 1
因為2>1，所以2在1後面FireFox的輸出則是：
目前正在比較 a = 1 與 b = 3
因為1<3，所以1在3前面
目前正在比較 a = 3 與 b = 2
因為3>2，所以3在2後面
目前正在比較 a = 1 與 b = 2
因為1<2，所以1在2前面 快捷的方式撰寫 compareFunction 到
明白了Compare Function撰寫方式後，我們可以用一些比較快捷的方式來撰寫：
// 當我們想要由小往大
arr.sort((a,b)=>a-b);// 當我們想要由大至小
arr.sort((a,b)=>b-a);
那當我們什麼都不寫的時候呢？
根據規範，預設的排序順序是根據字串的 Unicode 編碼位置（code points）而定，這也是為什麼許多人直接輸入 arr.sort() 仍然會去做排序（但通常排出來的跟想象中不一樣）的原因。
註：實際上 Python 也可以傳入 compareFunction，不過這邊不多討論，反正用了 lambda function 後，寫起來跟箭頭函數 87% 像。
基本上你只是想知道 Array 原型上的 sort 該怎麼用的話，你已經可以不必繼續往下看了！如果你對於為什麼不同瀏覽器的行為竟然那麼不一樣而感到困惑，請繼續往下看。
聊聊各家實作 Sort 的演算法
仔細看看 sort 的介紹
sort()方法會原地（in place）對一個陣列的所有元素進行排序，並回傳此陣列。排序不一定是穩定的（stable）。由於依賴執行環境的實作，所以並不能保證排序的時間及空間複雜度。
先來講講 原地（in place）
維基百科上針對 in place 算法有詳細的介紹，我們就直接懶人包告訴你，原地的算法會直接在原本的 array 上操作元素，這樣子不用額外的記憶體空間，也就是空間複雜度為 O(1) ，副作用就是會覆蓋原本的陣列。
再來講講什麼是穩定 （stable）
穩定的排序法再擁有相同 value 的狀況下，排序後的相依位置保證會跟排序前相同：
排序前：[1,3,2,5,6,3*] 、 排序後：[1,2,3,3*,5,6]
然而不穩定的排序法可能會造成
排序前：[1,3,2,5,6,3*] 、 排序後：[1,2,3*,3,5,6]
你可能會覺得 — 這有什麼不妥的嗎？
的確，在我剛開始學習排序演算法時，我其實挺不能理解穩定、不穩定會造成什麼問題，但我們觀看以下例子就可以很明顯的發現還是有些差別的。
var jojo= [
{
name:'Jonathan',
height:195
},{
name:'東方仗助',
height:180
},{
name:'Dio',
height:195
}
]如果你依照身高（height）做排序，穩定的排序可以確保 Jonathan 永遠排序在 Dio 前面，但是不穩定的排序可能最終的回傳結果會是 Dio 在 Jonathan 前面。
sort 的實作方式並沒有統一規範
由於依賴執行環境的實作，所以並不能保證排序的時間及空間複雜度。
對，這也代表一件事，不同的瀏覽器之間的實作方式並沒有統一，而且儘管是同個瀏覽器，也會因為版本的不同，而有不同的排序實作方式。
可能採用不同的演算法，各個演算法可能是 stable 也可能是 unstable 。
What is the stability of the Array.sort() method in different browsers?
- IE6+: stable
- Firefox < 3: unstable
- Firefox >= 3: stable
- Chrome < 70: unstable
- Chrome >= 70: stable
- Opera < 10: unstable
- Opera >= 10: stable
- Safari 4: stable
- Edge: unstable for long arrays
這個答案的整理很棒，這意味著即使你傳入同樣的 compareFunction ，最終結果在不同的瀏覽器，甚至是同個瀏覽器的不同版本都會有歧義。
由Mathias Bynens（他同時也是V8的開發者）提供的答案：
As of V8 v7.0 and Chrome 70, our
Array.prototype.sortimplementation is now stable. 🎉Previously, V8 used an unstable QuickSort for arrays with more than 10 elements. Now, V8 uses the stable TimSort algorithm.
可以發現說，在舊版本的 Chrome 中，他們透過快速排序法（quick sort）來實作排序，但在新的 Chrome 版本裡頭是使用 TimSort 來實作，兩者的時間複雜度都是 O(n log n) ，但是後者是穩定的排序法。
那我們刨根究底來看看 Firefox 的 stable sorting 是用什麼算法呢？答案就是合並排序法（merge sort）。時間複雜度也是 O(n log n)
https://bugzilla.mozilla.org/show_bug.cgi?id=224128 這個討論串還可以看到當時的討論。
就像上頭說的，ECMA並沒有明確規定 Array.prototype.sort 的方式到底需不需要 stable，所以掀起了一陣討論了。
為什麼多數人會使用 sort 來抨擊 JavaScript
這個 topic 聽起來是要與其他語言的使用者引戰，不過其實是想做一個 summary 啦，畢竟會抨擊 JavaScript ，代表真的有下去寫…吧…嗎。（還是雲程序員？）
1. 沒有搞清楚 sort 是高階函數
太多剛接觸 JavaScript 的同學，可能預設的 sort 的行為，對於函數是一級物件傳參回調不夠熟練。
2. 沒有閱讀文檔
因為太多語言的 sort 開箱即用，不會用這麼一個古怪的規則 — 「預設的排序順序是根據字串的 Unicode 編碼位置（code points）而定」。
3. 搞不懂 compare function
如果直接的把兩參數印出來只會更加的無解，需要知道的是， sort() 方法本來就與forEach()、map()、filter() 有一個根本上的差異，後者都是透過不停地迭代往前，但 sort() 並不是，試想 — 難道一輪迭代就能結束排序了嗎？
4. 被各家實作不一的 stable 、 unstable 搞死
這沒什麼好說的，就真的 weird ，如果要 stable 的排序，還是自己刻一個或是使用外部的函式庫會比較保險。
順帶一提上面講的都是不同階段的我啦
寫在最後
這篇文章本來想介紹除了 sort 以外的其他高階函數 forEach、map、filter，結果介紹 sort 竟然把篇幅全都佔據，看來 sort 的確滿有資格被做成 meme 打嘴炮的。
不過再 survey 資料的時候挺有趣的，以前在學習排序的相關知識時，並不會特別在乎實作方式，撰寫這篇文章的時候順便把以前學習演算法的知識又給回憶了一遍。
