FC19 Beating Array.Sort and Linq.Enumerable.OrderBy

In last episode (FC18 Stay away from string.CompareTo (beehiiv.com)), we discussed string.CompareTo in a performance sink hole, and how to replace it with StringComparer.Ordinal. But even after the change, Array.Sort(StringComparer.Ordinal) is still not fast enough, especially for smaller arrays. Another commonly used code path is Linq.Enumerable.OrderBy.

Let’s beat them both with this DIY version:

This version is using the QuickSort algorithm used by Linq.Enumerable.OrderBy implement, just calling string.CompareOrdinal directly.

Here is our performance benchmark:

Here we’re comparing five implementations of string sorting:

1. Linq.Enumerable.OrderBy using string.CompareTo.

2. Array.Sort using string.CompareTo

3. Linq.Enumerable.OrderBy using StringComparer.Ordinal

4. Array.Sort using StringComparer.Ordinal

5. DIY version of QuickSort calling string.CompareOrdinal directly.

Here are the results:

Linq.Enumerable.OrderBy implementation is allocating extra arrays. The default OrderBy implementation using string.CompareTo is the slowest.

The DIY QuickSort calling string.CompareOrdinal is the most efficient, and more optimizations are possible.