I hadn't planned on this being a perf-related PR, but as a happy accident, one of the issue numbers I was fixing up referred to a fix that could be made in LINQ's sorting implementation when a new Array.Sort overload was added. We ended up rejecting the proposal for that overload due to compatibility concerns, but the issue can be addressed similarly using the new span-based sorting methods we recently added.

The core sorting routine had been doing:

Array.Sort(keys, lo, hi - lo + 1, Comparer<int>.Create(CompareAnyKeys));

We have the CompareAnyKeys method, and we want to use it as the comparer for Array.Sort, but there's no overload that takes a Comparison<T>, so it's wrapped into a new IComparer<T>. There are a few issues with this. First, we're not only allocating a delegate for the CompareAnyKeys, we're also allocating an IComparer<T> to wrap it. Second, though, the Array.Sort<T> implementation actually works internally in terms of a Comparison<T>, so when it's given an IComparer<T>, it has to wrap its Compare method in a Comparison<T>. That means it ends up with a Comparison<T> wrapping the Compare method of an IComparer<T> that in turn invokes a Comparison<T>. Ugh. When we switch to using span:

new Span<int>(keys, lo, hi - lo + 1).Sort(CompareAnyKeys);

we pay for just one rather than two allocations, and we use the Comparison<T> directly rather than two additional levels of indirection.

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
using System.Linq;

public class Program
{
    static void Main(string[] args) => BenchmarkSwitcher.FromAssemblies(new[] { typeof(Program).Assembly }).Run(args);

    public Program()
    {
        var r = new Random(42);
        _array = new int[1_000];
        for (int i = 0; i < _array.Length; i++) _array[i] = r.Next();
    }

    private readonly int[] _array;

    [Benchmark]
    public void Sort()
    {
        foreach (int i in _array.OrderBy(i => i)) { }
    }
}