JavaScript实现的QuickSort为何远慢于原生array.sort()？

云上老周

2026-5-28

为什么手写快排比原生`array.sort()`慢这么多？

这是个非常典型的问题，核心原因可以拆解成这几点：

原生排序用的不是单纯的递归快排
主流JS引擎（比如Chrome的V8）的array.sort()是混合自适应算法：小数据集（比如长度小于22）用插入排序（小数据量下插入排序的常数项开销更低），大数据集用Timsort（融合归并排序和插入排序的稳定算法）或者改进版快排。而你手写的是最基础的递归快排，完全没有这些场景化优化。
Pivot选择的致命缺陷
你直接把数组第一个元素作为pivot，如果遇到有序/逆序的数组（或者测试数据刚好有偏向性），每次分区都会变成n-1和0的极端情况，时间复杂度直接从O(n log n)退化成O(n²)。而原生实现会用三数取中（选首、中、尾三个元素的中位数当pivot）或者随机选择pivot，从根源避免最坏情况。
内存分配与拷贝的巨量开销
你的实现每次递归都会创建新的left和right数组，还会用concat拼接结果——这意味着每一层递归都要做数组拷贝，10万条数据的递归深度下，内存分配和垃圾回收的开销会被无限放大。而原生sort()是原地排序（直接修改原数组，不需要额外创建大量新数组），内存效率高得多。
引擎级别的底层优化
原生array.sort()是用C++这类底层语言实现的，经过了极致优化：比如循环展开、缓存友好的内存访问模式、汇编级别的指令优化。而你手写的JS代码，即使经过JIT编译，在循环效率、数组操作速度上也远不如原生实现。
递归栈的额外开销
基础递归快排在处理大数据集时，递归深度会达到O(log n)（最坏情况O(n)），这会带来额外的栈帧开销。而原生实现很多用迭代方式实现排序，或者做了尾递归优化，彻底规避了这部分开销。