看到「Stable Array.prototype.sort」這篇在講 JavaScript 規格書裡的 sort...
本來 JavaScript 的規格書裡，各種 sort 都沒有保證 stable，而在「[Normative] Make Array.prototype.sort stable #1340」與「[Normative] Make %TypedArray%.prototype.sort stable #1433」這兩個地方則有了變化，提案在規格裡加入 stable 的要求，可以減少開發者因為不知道 unstable 而造成的問題...
Firefox 則是很久前就決定使用 Merge sort 了 (看了一下，當時還在從 Firebird 轉換名稱到 Firefox 的時期)：「Array.sort isn't a stable sort (switch to MergeSort)」。
另外這篇也剛好提到了 V8 使用 Timsort 當作 stable sorting algorithm，之前就有看到但發現沒在 blog 上提過...
Timsort 是 1993 年發明出來的演算法，與 Merge sort 的情況類似，除了 stable 外，還可以保證最差的情境下的時間複雜度是 
：
Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.
這個演算法的重點是善用已經排好的子序列，藉此降低記憶體操作次數而提昇效能，符合真實環境裡常見到的資料：
The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.
除了 V8 採用這個演算法以外，其他常見的包括了 Python 與 Android 上的 Java SE：
Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, and Google Chrome.
