Array.sort() 排序

在 JavaScript 中，我们会使用 Array.sort() 来进行排序，一般的用法如下：

array.sort((a, b) => a - b); // 升序

array.sort((a, b) => b - a); // 降序

问题是：为什么 a - b 得到的是升序，而 b - a 却能得到降序呢，因为 a - b 和 b -a 都存在结果为正或负的情况，内部到底是怎么计算的呢？

在新版本的的 V8 引擎中，使用的是 TimSort 算法，我们主要看旧版本的 V8 引擎中的排序算法。 在旧版本的 V8 引擎中，会根据数组的长度来决定使用什么排序，如果数组的长度大于 22（各版本不一致） 则会使用快速排序，否则使用插入排序。

插入排序的大致逻辑：

void InsertionSort(Handle<JSArray> array, Handle<Object> comparefn) {
    for (int i = 1; i < array->length(); i++) {
        for (int j = i; j > 0; j--) {
            Handle<Object> a = array->get(j - 1);
            Handle<Object> b = array->get(j);
            int compareResult = CallCompareFunction(comparefn, a, b);
            if (compareResult > 0) {
                // 如果比较结果为正数，则交换元素位置
                array->set(j - 1, b);
                array->set(j, a);
            } else {
                break;
            }
        }
    }
}

假设有一个数组： [3, 2, 1]，

使用 array.sort((a, b) => a - b) 进行排序，那么排序的过程如下：

1. i = 1, j = 1，a = 3, b = 2，compareResult = 1，结果大于 0，交换位置，数组变为 [2, 3, 1]
2. i = 2, j = 2，a = 3, b = 1，compareResult = 2，结果大于 0，交换位置，数组变为 [2, 1, 3]
3. i = 2, j = 1，a = 2, b = 1，compareResult = 1，结果大于 0，交换位置，数组变为 [1, 2, 3]

所以最终的结果是升序的 [1, 2, 3]。

同理，array.sort((a, b) => b - a) 的排序过程如下：

1. i = 1, j = 1，a = 3, b = 2，compareResult = -1，结果小于 0，不交换位置，结束。
2. i = 2, j = 2，a = 2, b = 1，compareResult = -1，结果小于 0，不交换位置，结束。

最终的结果是降序的 [3, 2, 1]。

参考：

https://v8.dev/blog/array-sort