“455 分发饼干”中排序算法的时间复杂度问题

背景

在做 455. 分发饼干 - 力扣（LeetCode） 时，思路就是让大饼干去满足大胃口的孩子。这就需要对小孩子的胃口值和饼干的大小进行排序，于是我写了一个经典的冒泡排序函数：

function bubbleSort(arr: number[]): number[] {
    for (let i = 0; i < arr.length - 1; i ++) {
        for (let j = 0; j < arr.length - i - 1; j ++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }

    return arr
}

在提交后发现第23个测试用例超时了：所有的胃口都是4，所有的饼干尺寸都为1

解决

于是不用自己写的冒泡排序，转而用 `.sort` 方法

g = g.sort((a, b) => a - b)
s = s.sort((a, b) => a - b)

为什么会这样？

很疑惑：该用例中的 g 和 s 数组中的每一项都是同一个数，此时的数组算是有序数组，用冒泡排序的时间复杂度是 O(n)，按说应该很快了 ... ...

推测 `.sort` 应该是经过某些优化，这个问题先这样吧 😢