什么是 Array.prototype.sort() 时间复杂度？

Question

根据 Mozilla 文档：

排序的时间和空间复杂度无法保证，因为它取决于实现。

假设它不是至少安全O(n^2)吗？有没有关于它是如何实施的更详细的数据？谢谢。

Answer 1

Firefox 使用合并排序。Chrome 从 70 版开始，使用称为Timsort的合并排序和插入排序的混合。

归并排序的时间复杂度为O(n log n). 虽然规范没有指定要使用的排序算法，但在任何严重的环境中，您可能会期望对较大的数组进行排序所花费的时间不会超过O(n log n)（因为如果这样做，将很容易更改为更快的算法，例如归并排序，或其他一些对数线性方法）。

虽然像合并排序这样的比较排序的下限为O(n log n)（即它们至少需要这么长时间才能完成），但 Timsort 利用已排序数据的“运行”优势，因此下限为O(n)。

Answer 2

理论与实践：理论上，理论与实践没有区别，但在实践中却存在差异。

• 理论：一切都清楚了，但没有任何作用；
• 实践：一切都有效，但什么都不清楚；
• 有时理论与实践相结合：没有任何效果，也没有什么是清楚的。

大 O 表示法非常适合评估算法的可扩展性，但无法提供直接比较算法实现之间性能的方法......

典型的例子是浏览器中 Array.sort() 的实现。尽管 Timsort 具有比合并排序更好的 Big O 配置文件（请参阅https://www.bigocheatsheet.com/），但实证测试表明，Chrome V8 引擎中 Timsort 的实现平均明显优于 Firefox 中合并排序的实现。

下面的图表分别显示两组数据点：

• 蓝色数据是 Array.sort() 对随机填充整数的随机长度数组（从 100 到 500,000 个元素）的 500 个测试用例的性能。曲线以 N * Log( N ) 的形式显示数据的中位数，虚线以 N * Log( N ) 的形式显示 95% 的边界。也就是说，95% 的数据点位于这些曲线之间。
• 橙色数据显示了 Array.sort() 对于大部分已排序数组的性能。具体来说，数组中大约 2% 的值被重新随机化，然后再次应用 Array.sort()。在这种情况下，实线和虚线是性能的线性度量，而不是对数。

此外，大 O 表示法提供了算法可扩展性的一般经验法则，但没有解决可变性问题。Timsort 算法的 Chrome V8 实现在执行方面比 Firefox 合并排序具有更大的可变性，尽管 Timsort 具有更好的 Big O 配置文件，但即使 Timsort 的最佳时间也不比合并排序的最差时间更好。冒着引发宗教战争的风险，这并不意味着 Timsort 比合并排序差，因为这可能只是 Firefox 的 JavaScript 实现获得了更好的整体性能。

上面图表的数据是根据我的 Acer Aspire E5-5775G Signature Edition 上的以下代码生成的，该版本具有 Intel Core i5-7200U CPU @2.50GHz 和 8GB RAM。然后将数据导入 Excel，分析 95% 的边界范围，然后绘制图表。图表上的轴刻度已标准化，以便于视觉比较。

  function generateDataPoints( qtyOfTests, arrayRange, valueRange, nearlySortedChange ) {
  
    let loadingTheArray = [];
    let randomSortMetrics = [];
    let nearlySortedMetrics = [];
    
    for ( let testNo = 0; testNo < qtyOfTests; testNo++ ) {
      if ( testNo % 10 === 0 ) console.log( testNo );
      
      // Random determine the size of the array given the range, and then
      // randomly fill the array with values.
      let testArray = [];      
      let testArrayLen = Math.round( Math.random() * ( arrayRange.hi - arrayRange.lo ) ) + arrayRange.lo;
      
      start = performance.now();
      for ( let v = 0; v < testArrayLen; v++ ) {
        testArray[ v ] = Math.round( Math.random() * ( valueRange.hi - valueRange.lo ) ) + valueRange.lo;
      }
      end = performance.now();
      
      loadingTheArray[ testNo ] = { x: testArrayLen, y: Math.floor( end - start ) };
      
      // Perform the sort and capture the result.
      start = performance.now();
        testArray.sort( (a, b ) => a - b );
      end = performance.now();
      
      randomSortMetrics[ testNo ] = { x: testArrayLen, y: Math.floor( end - start ) };
      
      // Now, let's change a portion of the sorted values and sort again.
      let qtyOfValuesToChange = testArrayLen * nearlySortedChange;
      for ( let i = 0; i < qtyOfValuesToChange; i++ ) {
        let v = Math.round( Math.random() * testArrayLen );
        testArray[ v ] = Math.round( Math.random() * ( valueRange.hi - valueRange.lo ) ) + valueRange.lo;
      }
      
      start = performance.now();
        testArray.sort( (a, b ) => a - b );
      end = performance.now();
      
      nearlySortedMetrics[ testNo ] = { x: testArrayLen, y: Math.floor( end - start ) };

    }
    
    return  [ loadingTheArray, randomSortMetrics, nearlySortedMetrics ];
    
  }
  
  // Let's start running tests!
  let arraySizeRange = { lo: 100, hi: 500000 };
  let valueRange = { lo: 0, hi: 2 ** 32 - 1 };
  let results = generateDataPoints( 500, arraySizeRange, valueRange, 0.02 );
  
  
  let tabFormat = 'No Of Elements\tTime to Load Array\tFull Sort\tMostly Sorted\n';
  for ( let i = 0; i < results[0].length; i++ ) {
    tabFormat += `${results[0][i].x}\t${results[0][i].y}\t${results[1][i].y}\t${results[2][i].y}\n`;
  }
  console.log( tabFormat );

结论是，基于 Big O 表示法，算法的性能表面上会更好，但有许多因素驱动其整体性能，更好的 Big O 并不一定会转化为更好的性能……

Answer 3

这取决于浏览器/引擎。

\n

自V8 v7.0和Chrome 70开始使用Timsort算法。
\n对于较小的数组，时间复杂度为 O(n)，空间复杂度为 0(1)。\n对于较大的数组，时间复杂度为 O(nlog(n))，空间复杂度为 O( n).

\n

旧版本的 V8 使用快速排序，它会检查小型数组（最多 10 个元素）。\n因此，对于较小的数组，时间复杂度为 O(n^2)，空间复杂度为 O(1)。
\n对于较大的数组，时间复杂度为 \xce\x98(n log(n)) （平均情况），空间复杂度为 O(log(n))

\n