为什么C#内置排序函数Array.Sort()如此高效？比自定义快速排序快那么多？

Question

Array.Sort()使用的是快速排序+堆排序，我在网上找到的几个C#实现的泛型QuickSort()函数都比内置的Array.Sort()慢很多。（其中我找到最快的实现是：https://blog.csdn.net/sarono/article/details/83876260）

我又在https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs上面直接Copy了Array.Sort()的源码到我的项目中做比较，发现当这个内置函数变成自定义函数之后，它慢得更离谱

以下在vs2019的release模式下测试的1kw个<int>类型数据排序的结果：

三个函数都是泛型版本的

第一个是一般的自定义函数的QuickSort，

第二个是直接复制的C#Array.Sort()的源码作为自定义函数，

第三个是直接调用C#内置Array.Sort()

显然前两个都不如最后的快，更离谱的是第二个居然比第一个更慢了。第二个和第三个明明是同一源码

虽然泛型数据的比较要调用CompareTo()函数，相比更慢。但在大家都是泛型实现的情况下，为什么还会造成这种速度上的差距？为什么内置的Array.Sort()这么快呢？

Answer 1

似乎找到原因了，是C#的排序函数调用了一个叫做TrySZSort的函数：它可以对int这种原生类型进行速度更快的快排。当对象不支持TrySZSort时，才会继续往下调用ArraySortHelper<T>.Default.Sort(array, index, length, comparer)

其中后者因为用到了comparer和一些奇奇怪怪的异常检测，所以效率肯定是更低的。而我的测试中，第二个直接复制的源码，其实只是复制了ArraySortHelper中的Sort函数，而忽略了TrySZSort，固然对于int这种类型，是比直接调用List.Sosrt要更快的（因为它会先尝试使用更快的TraySZSort）

而对第一个函数，就更不用说了，虽然已经在C#语法上榨干了性能，但由于是泛型排序它还是不可避免地用到了泛型比较方法CompareTo()等，速度上还是没有办法与TrySZSort相比

 

所以这个问题，由于List.Sort()会优先对int类型进行优化，事实上并不是泛型之间的比较，而是泛型方法与非泛型方法（TrySZSort）之间的比较，这固然是要被后者秒杀的……

 

对这问题有兴趣的朋友可以看看下面这两个文章：

http://blog.zhaojie.me/2010/01/sort-array-linq-2-array-sort.html

https://www.cnblogs.com/showjim/archive/2012/05/11/2496072.html

 

谢谢两位的回答