貌似前端圈一直以來流傳著一種誤解：前端用不到算法知識。長久以來，大家或許都曾受這種說法的影響。直到前陣子遇到一個產品需求，回過頭來看，發現事實并非如此。

前端排序

前端排序的場景

前端將排序條件作為請求參數傳遞給后端，后端將排序結果作為請求響應返回前端，這是一種常見設計。但是對于有些產品則不是那么適用。

試想一個場景：你在使用美食類APP時，是否會經常切換排序方式，一會兒按照價格排序，一會兒按照評分排序。

實際生產中，受限于服務器成本等因素，當單次數據查詢成為整體性能瓶頸時，也會考慮通過將排序在前端完成的方式來優化性能。

排序算法

感覺這個沒什么介紹的必要，作為計算機科學的一種基礎算法，描述就直接照搬 Wikipedia。

這里存在這一段內容純粹是為了承(cou)上(man)啟(zi)下(shu)。

JavaScript的排序

既然說到前端排序，自然首先會想到JavaScript的原生接口 Array.prototype.sort。

這個接口自 ECMAScript 1st Edition 起就存在。讓我們看看最新的規范中關于它的描述是什么樣的。

Array.prototype.sort規范

Array.prototype.sort(compareFn)

顯然，規范并沒有限定 sort 內部實現的排序算法是什么。甚至接口的實現都不需要是 穩定排序 的。這一點很關鍵，接下來會多次涉及。

在這樣的背景下，前端排序這件事其實取決于各家瀏覽器的具體實現。那么，當今主流的瀏覽器關于排序是怎么實現的呢？接下來，我們分別簡單對比一下 Chrome、Firefox 和 Microsoft Edge。

Chrome中的實現

Chrome 的JavaScript引擎是 v8。由于它是開源的，所以可以直接看源代碼。

整個 array.js 都是用 JavaScript 語言實現的。排序方法部分很明顯比曾經看到過的快速排序要復雜得多，但顯然核心算法還是 快速排序。算法復雜的原因在于 v8 出于性能考慮進行了很多優化。(接下來會展開說)

Firefox中的實現

暫時無法確定Firefox的JavaScript引擎即將使用的數組排序算法會是什么。[3]

按照現有的信息，SpiderMoney 內部實現了 歸并排序。

Microsoft Edge中的實現

Microsoft Edge 的JavaScript引擎 Chakra 的核心部分代碼已經于2016年初在Github開源。

通過看源代碼可以發現，Chakra 的數組排序算法實現的也是 快速排序。而且相比較于 v8，它就只是實現了純粹的快速排序，完全沒有 v8 中的那些性能優化的蹤影。

JavaScript數組排序的問題

眾所周知，快速排序 是一種不穩定的排序算法，而 歸并排序 是一種穩定的排序算法。由于不同引擎在算法選擇上的差異，導致前端依賴 Array.prototype.sort 接口實現的JavaScript代碼，在瀏覽器中實際執行的排序效果是不一致的。

排序穩定性的差異需要有特定的場景觸發才會存在問題；在很多情況下，不穩定的排序也不會造成影響。

假如實際項目開發中，對于數組的排序沒有穩定性的需求，那么其實看到這里為止即可，瀏覽器之間的實現差異不那么重要。

但是若項目要求排序必須是穩定的，那么這些差異的存在將無法滿足需求。我們需要為此進行一些額外的工作。

舉個例子：

某市的機動車牌照拍賣系統，最終中標的規則為：

    1. 按價格進行倒排序；

    2. 相同價格則按照競標順位（即價格提交時間）進行正排序。

排序若是在前端進行，那么采用快速排序的瀏覽器中顯示的中標者很可能是不符合預期的

探究差異的背后

尋找解決辦法之前，我們有必要先探究一下出現問題的原因。

Chrome為什么采用快速排序

其實這個情況從一開始便存在。

Chrome測試版 于2008年9月2日發布，然而發布后不久，就有開發者向 Chromium 開發組提交#90 Bug反饋v8的數組排序實現不是穩定排序的。

這個Bug ISSUE討論的時間跨度很大。一直到2015年11月10日，仍然有開發者對v8的數組排序實現問題提出評論。

同時我們還注意到，該ISSUE曾經已被關閉。但是于2013年6月被開發組成員重新打開，作為 ECMAScript Next 規范討論的參考。

而es-discuss的最后結論是這樣的

正如本文前段所引用的已定稿 ECMAScript 2015 規范中的描述。

時代特點

IMHO，Chrome發布之初即被報告出這個問題可能是有其特殊的時代特點。

上文已經說到，Chrome第一版 是 2008年9月 發布的。根據statcounter的統計數據，那個時期市場占有率最高的兩款瀏覽器分別是 IE(那時候只有IE6和IE7) 和 Firefox，市場占有率分別達到了67.16%和25.77%。也就是說，兩個瀏覽器加起來的市場占有率超過了90%。

而根據另一份瀏覽器排序算法穩定性的統計數據顯示，這兩款超過了90%市場占有率的瀏覽器都采用了穩定的數組排序。所以Chrome發布之初被開發者質疑也是合情合理的。

符合規范

從Bug ISSUE討論的過程中，可以大概理解開發組成員對于引擎實現采用快速排序的一些考量。

其中一點，他們認為引擎必須遵守ECMAScript規范。由于規范不要求穩定排序的描述，故他們認為 v8 的實現是完全符合規范的。

性能考慮

另外，他們認為 v8 設計的一個重要考量在于引擎的性能。

快速排序 相比較于 歸并排序，在整體性能上表現更好：

更高的計算效率。快速排序 在實際計算機執行環境中比同等時間復雜度的其他排序算法更快（不命中最差組合的情況下）
更低的空間成本。前者僅有O(