C＃List <T> .Sort-为什么默认实现具有如此好的性能？

Question

两次过载之间的时间差List<T>.Sort(...)。

        List<int> list = new List<int>();
        Random rand = new Random();

        for (int i = 0; i < 20_000_000; i++)
        {
            list.Add(rand.Next());
        }

        Stopwatch watch = new Stopwatch();
        watch.Start();

        //list.Sort(); // 1.77 sec
        list.Sort((n1, n2) => n1.CompareTo(n2)); // 5.80 sec

        watch.Stop();
        Console.WriteLine(watch.Elapsed.TotalSeconds);

为什么第二种形式这么慢？

Answer 1

list.Sort()最终将调用Array.Sort，对于未传入比较器的情况，它具有特定的优化。

这是在这篇博客文章中讨论的：

.NET中排序的核心是一个称为TrySZSort的外部本机函数。在幕后，Array.Sort调用CLR本身的一部分C ++代码。此代码已进行了优化。

使用list.Sort((n1, n2) => n1.CompareTo(n2))表单时，您将失去以下经过高度优化的实现：

还值得注意的是，TrySZSort仅针对默认比较器被调用。如果提供自定义比较器，则不会使用它。对于自定义比较器，在托管代码内部执行与TrySZSort中相似的排序算法。当然，这缺乏非托管代码的所有优势，并且错过了大多数本机优化。