JavaScript中Cocktail Sort为何在降序数组上慢于Bubble Sort？

我在测试排序算法性能时，输入数据是降序排列的数字数组。按理论预期，鸡尾酒排序（Cocktail Sort）在这类场景下应该略快于冒泡排序，但在JavaScript中测试时，几乎每次都是鸡尾酒排序更慢。将代码改写为C++后，鸡尾酒排序始终比冒泡排序更快，且数组越大两者的时间差距越明显。

以下是我的JavaScript测试代码：

function cocktailTP(array) {
    const startTime = performance.now();
    let swapped = false;
    let start = 0;
    let end = array.length - 1;
    let temp;

    do {
        swapped = false;
        for (let i = start; i < end; i++) {
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = true;
            }
        }
        end--;

        for (let j = end; j > start; j--) {
            if (array[j] < array[j - 1]) {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                swapped = true;
            }
        }
        start++;
    } while (swapped);

    const endTime = performance.now();
    const executionTime = endTime - startTime;
    console.log(`Cocktail sort took ${executionTime} milliseconds to sort an array of ${array.length} elements.`);
}

function bubbleSortTP(array) {
    const startTime = performance.now();
    for (let i = 0; i < array.length - 1; i++) {
        for (let j = 0; j < (array.length - i - 1); j++) {
            if (array[j] > array[j + 1]) {
                const temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    const endTime = performance.now();
    const executionTime = endTime - startTime;
    console.log(`Bubble sort took ${executionTime} milliseconds to sort an array of ${array.length} elements.`);
}

// 生成降序测试数组（修正原代码空数组问题）
let arr = Array.from({length: 10000}, (_, i) => 10000 - i);
const firstCopy = arr.slice();
const secondCopy = arr.slice();
cocktailTP(firstCopy);
bubbleSortTP(secondCopy);

出现这种JS与C++结果相反的情况，核心原因有三点：

1. JavaScript引擎的JIT优化差异 #

V8等主流JS引擎对结构简单的嵌套循环（比如冒泡排序的两层for循环）优化更彻底：这类循环控制流规整，容易被JIT编译器识别为热点代码，进而生成高度优化的机器码。而鸡尾酒排序的do-while嵌套两个方向的for循环，控制流更复杂，JIT难以做深度优化，最终生成的执行代码效率远低于冒泡排序。

相比之下，C++的静态编译器（如GCC、Clang）可以在编译阶段就对复杂循环做更彻底的分析和优化，比如提前预判无意义的循环分支，生成更高效的机器指令。

2. 内存访问的缓存局部性差异 #

冒泡排序是单向顺序遍历数组，内存访问完全符合CPU缓存的局部性原理，缓存命中率极高，能大幅减少CPU等待内存数据的时间。

而鸡尾酒排序需要先从左到右、再从右到左来回切换遍历方向，频繁的方向切换会打破缓存的连续性，导致更多的缓存miss（缓存未命中），CPU不得不等待从主内存加载数据，直接拖慢了执行速度。

3. 降序场景下的无效执行开销 #

在完全降序的数组中，鸡尾酒排序的反向遍历分支完全没有意义：此时数组左大右小，反向遍历时array[j] < array[j-1]的判断永远不成立，不会产生任何交换操作，但这部分循环的比较、条件判断步骤依然会完整执行，等于平白增加了额外的执行开销。

在C++中，静态编译器可能会通过死代码消除优化，直接去掉这部分无效循环；但JavaScript的JIT编译器在动态执行时，很难提前预判这部分分支的无效性，只能完整执行所有循环步骤，进一步拉大了与冒泡排序的性能差距。

内容的提问来源于stack exchange，提问作者tlapka