Stable and Unstable Sorting for Structs in .NET
03/16/2024
8 minutes
Sorting items of a collection is a common task that .NET developers perform. A collection is a data structure that stores multiple values, such as an array, a list, a dictionary, etc.
One common way to sort items of a collection in .NET 8 (and previous .NET versions) is by using LINQ’s OrderBy extension method. LINQ stands for Language Integrated Query, and it is a set of features that allow you to query and manipulate data in various ways. For example, you can use OrderBy to sort a list of numbers:
// Create a list of numbers List<int> numbers = [3, 1, 2]; // Sort the list using OrderBy var sorted = numbers.OrderBy(x => x);
Another way to sort items of a collection is by using Array.Sort method. This method works on arrays, which are fixed-size collections of values. For example, you can use Array.Sort to sort an array of numbers in ascending order:
// Create an array of numbers int[] numbers = new int[] {5, 3, 7, 1, 9}; // Sort the array using Array.Sort Array.Sort(numbers);
I have recently learned that Array.Sort is an unstable, while OrderBy is a stable sort. A sort is stable if it preserves the order of items which have equal sorting keys.
Stability is important when we want to sort by multiple criteria. For example, if we want to sort the list of names and ages by age first, and then by name, we can use a stable sort twice. First, we sort by name using a stable sort. Then, we sort by age using another stable sort. The result will be a list that is sorted by age, and within each age group, the names are sorted alphabetically. If we use an unstable sort, the order of names within each age group may be different from the original order.
Stability depends on the algorithm used for sorting. Array.Sort uses introsort, which is a hybrid algorithm that combines quicksort, heapsort, and insertion sort. Its documentation points out that it is unstable. LINQ's OrderBy remarks that it is a stable sort. One might remember that LINQ offers a ThenBy or ThenByDescending extension, that requires the sorting mechanism to be stable.
Many line-of-business (LOB) applications do not require the stability property of sorting. That raises the following questions naturally:
Is an unstable sort inherently faster?
Can we create a LINQ extension method that implements unstable sort?
The previous blog post has answered these questions when sorting reference types, which is the more common case for LOB application. This blog post aims to answer both of these questions for value types.
Performance Comparison
First, let's compare .NET's built-in sorting algorithms. For anyone intending to replicate the results, I am using a Windows 11, x64 machine with .NET 8 RC 2. The test machine has an Intel i7 1255U CPU. To run the benchmarks, I use BenchmarkDotNet version 0.13.9.
These performance comparisons can be sensitive to the inputs. My intention is to create test data that resembles data that is typically sorted in applications I have worked with. These are the preconditions:
Sorting does not require stability.
Small collections have <50 items and large collections >1000 items, but not significantly different in magnitude.
In this post I will focus on testing with value types, while previous post has covered these questions for reference types.
For the sample DTO I implemented DataStruct that has 2 integer fields: Number which can be used to order the items and OriginalOrder that indicates the original order. With OriginalOrder the stability of the sorting algorithm can be validated: when it decreases for two consecutive items after sorting, the algorithm is unstable. When no such case is observed, it cannot be determined if it is stable or unstable.
public record struct DataStruct(int Number, int OriginalOrder) : IComparable<DataStruct> { public int CompareTo(DataStruct other) => Number - other.Number; }
The type implements IComparable<T> and it also has a separate class (exluded here for brevity) that implements IComparer<T> interface. This gives an opportunity to explore some of the overloads that Array.Sort and Order/OrderBy offer.
To answer the first question, the following test data is generated. An array of 1000 DataStruct is prepared. Each has the Number property set randomly between 0 and 99. The OriginalOrder is set as well consecutively from 0 to 999.
The benchmarking methods are shown below:
[Benchmark] public DataStruct[] LinqOrderComparer() => _input.Order(_comparer).ToArray(); [Benchmark] public DataStruct[] LinqOrderComparerable() => _input.Order().ToArray(); [Benchmark] public DataStruct[] LinqOrderBy() => _input.OrderBy(x => x.Number).ToArray(); [Benchmark] public DataStruct[] ArraySortComparer() { var unstableResults = _input.ToArray(); Array.Sort(unstableResults, _comparer); return unstableResults; } [Benchmark] public DataStruct[] ArraySortComparerable() { var unstableResults = _input.ToArray(); Array.Sort(unstableResults); return unstableResults; }
One observation to make: all benchmarking methods create and return a new array. Array.Sort based tests do this as an upfront cost - copy all items to a new array that gets sorted. The LINQ based solutions do this as the last step to force execution. While this will make that memory requirements double (they internally also allocate a buffer for the sorting), in real-life LINQ queries a developer would likely call a ToList() regardless as the last step of the code.
Benchmark results for 1000 items:
| Method | Mean | Error | StdDev | Gen0 | Gen1 | Allocated | |---------------------- |----------:|----------:|----------:|-------:|-------:|----------:| | LinqOrderComparer | 19.290 us | 0.3760 us | 0.4330 us | 3.2043 | 0.0916 | 19.77 KB | | LinqOrderComparerable | 13.647 us | 0.1142 us | 0.1013 us | 3.2196 | 0.0916 | 19.77 KB | | LinqOrderBy | 24.789 us | 0.2178 us | 0.2037 us | 3.8452 | 0.1221 | 23.7 KB | | ArraySortComparer | 7.780 us | 0.0597 us | 0.0558 us | 1.2817 | - | 7.9 KB | | ArraySortComparerable | 5.938 us | 0.0503 us | 0.0446 us | 1.2741 | - | 7.84 KB |
For reference types, the Array.Sorting IComperable<T> gives the best performance characteristics.
Creating an 'unstable' Sorting Extension Method
A key difference to reference types is that when the struct implements IComparable<T>, the sort is significantly faster compared passing a Func<T,TKey> selector as an argument. With this in mind, I will not detail the implementation of Iteration 1 to Iteration 6 in this post as they are already covered in the previous post. For reference, Iteration 1 and Iteration 6 are included in the performance benchmarks. Those iterations focus on building an unstable extension method using a key selector function.
In this post, I will present an overload of ToOrderedByArray method that requires the type to be sorting IComparable<T>.
Iteration 7
This iteration of ToOrderedByArray uses the plain Array.Sort. The only additional knowledge it has is to return OrderedArray<T> which allows for further optimizations as described in the previous post.However, this ToOrderedByArray requires the ordered items to implement IComparable<T>. The DataStruct implements this interface.
public static OrderedArray<T> ToOrderedByArray<T>(this IEnumerable<T> source) where T : struct, IComparable<T> { var buffer = source.ToArray(); Array.Sort(buffer); return new OrderedArray<T>(buffer); }
The performance results for sorting 1000 items:
| Method | Mean | Error | StdDev | Gen0 | Gen1 | Allocated | |---------------------- |----------:|----------:|----------:|-------:|-------:|----------:| | LinqOrderComparer | 19.290 us | 0.3760 us | 0.4330 us | 3.2043 | 0.0916 | 19.77 KB | | LinqOrderComparerable | 13.647 us | 0.1142 us | 0.1013 us | 3.2196 | 0.0916 | 19.77 KB | | LinqOrderBy | 24.789 us | 0.2178 us | 0.2037 us | 3.8452 | 0.1221 | 23.7 KB | | ArraySortComparer | 7.780 us | 0.0597 us | 0.0558 us | 1.2817 | - | 7.9 KB | | ArraySortComparerable | 5.938 us | 0.0503 us | 0.0446 us | 1.2741 | - | 7.84 KB | | 'Iteration 1' | 11.069 us | 0.0835 us | 0.0740 us | 1.2817 | - | 7.92 KB | | 'Iteration 6' | 9.612 us | 0.0672 us | 0.0628 us | 1.2817 | - | 7.87 KB | | 'Iteration 7' | 5.422 us | 0.0464 us | 0.0434 us | 1.2817 | - | 7.87 KB |
The performance results for sorting 50 items:
| Method | Mean | Error | StdDev | Gen0 | Allocated | |---------------------- |---------:|---------:|---------:|-------:|----------:| | LinqOrderComparer | 607.8 ns | 11.86 ns | 12.18 ns | 0.1984 | 1248 B | | LinqOrderComparerable | 477.8 ns | 5.28 ns | 4.94 ns | 0.1984 | 1248 B | | LinqOrderBy | 662.2 ns | 9.51 ns | 8.43 ns | 0.2346 | 1472 B | | ArraySortComparer | 253.6 ns | 3.62 ns | 3.39 ns | 0.0777 | 488 B | | ArraySortComparerable | 207.9 ns | 1.50 ns | 1.41 ns | 0.0675 | 424 B | | 'Iteration 1' | 323.5 ns | 3.08 ns | 2.88 ns | 0.0815 | 512 B | | 'Iteration 6' | 390.7 ns | 3.57 ns | 2.98 ns | 0.0725 | 456 B | | 'Iteration 7' | 213.0 ns | 3.26 ns | 3.05 ns | 0.0725 | 456 B |
Conclusion
In this post, I have explored wrapping an unstable sort operation in a LINQ extension method. The goal is to sort small (<1000) sized inputs of value types. I have explored differences in performance compared to using reference types. I have presented one additional iteration on top of the previously discussed ToOrderedByArray methods. This iteration focuses on handling value types. For the best performance the value types require implementing IComparable<T>.
While it is possible to create an unstable sort for value types and reference types as well, having both implementations present in the codebase will likely require different type constraints, so that always the right one gets bind by the C# compiler.