Sorting Stable Unstable

Readme.md

Stable and Unstable Sorts in .NET

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 names alphabetically:

// Create a list of names
List<string> names = new List<string>() { "Charlie", "Alice", "Bob" };

// Sort the list by name using OrderBy
var sortedNames = names.OrderBy(name => name);

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?

This blog post aims to answer both of these questions.

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.

I will both test sorting value and reference types. In this post I will focus on reference types, which are the more common in the use-cases I pursue. A future post will focus on value types.

For the sample DTO I implemented DataClass that has 2 integer fields: Number which can be used to order the items and OriginalOrder that indicates the original order. This way one can check if the used sorting is stable or not. When OriginalOrder decreases for two consecutive items after sorting, the algorithm is unstable. When no such case is observed, it can be either stable or unstable that looks like stable by chance.

public record class DataClass(int Number, int OriginalOrder) : IComparable<DataClass>
{
	public int CompareTo(DataClass? 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 DataClass instances 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 DataClass[] LinqOrderComparer() => _input.Order(_comparer).ToArray();

[Benchmark]
public DataClass[] LinqOrderComparerable() => _input.Order().ToArray();

[Benchmark]
public DataClass[] LinqOrderBy() => _input.OrderBy(x => x.Number).ToArray();

[Benchmark]
public DataClass[] ArraySortComparer()
{
	var unstableResults = _input.ToArray();
	Array.Sort(unstableResults, _comparer);
	return unstableResults;
}

[Benchmark]
public DataClass[] 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	62.43 us	0.878 us	0.778 us	3.1738	-	19.77 KB
LinqOrderComparerable	80.86 us	0.707 us	0.662 us	3.1738	-	19.77 KB
LinqOrderBy	35.45 us	0.433 us	0.405 us	3.8452	0.1221	23.7 KB
ArraySortComparer	17.54 us	0.222 us	0.208 us	1.2817	-	7.9 KB
ArraySortComparerable	31.90 us	0.425 us	0.398 us	1.2207	-	7.84 KB

For reference types, the Array.Sort with a comparer gives the best performance characteristics.

Creating an 'unstable' Sorting Extension Method

This section creates an extension mehtod that leverages the findings of the previous section. The goal is to create an OrderBy extension method that takes an IEnumerable<T> source and a Func<TSource, TKey> function for selecting the key.

Iteration 1

An initial solution is to create a method named ToOrderedByArray. A disadvantage of this implementation is that it needs to call the keySelector function on every comparison. This makes it inefficient. Another disadvantage is that the TKey is restricted to returnint value. Without this restriction, the solution is much slower in performance (~20% slower mean execution times).

public static T[] ToOrderedByArray<T>(this IEnumerable<T> source, Func<T, int> keySelector)
{
    var buffer = source.ToArray();
    Array.Sort(buffer, new GenericKeySelectedComparer<T>(keySelector));
    return buffer;
}

//...
public sealed class GenericKeySelectedComparer<T>(Func<T, int> keySelector) : IComparer<T>
{
	public int Compare(T? x, T? y) => keySelector(x) - keySelector(y);
}

Results with 1000 element long input:

Method	Mean	Error	StdDev	Gen0	Gen1	Allocated
'Iteration 1'	24.63 us	0.221 us	0.196 us	1.2817	-	7.92 KB

Iteration 2

In the second iteration of ToOrderedByArray, the comparer is avoided and instead a Span sort is used. The key selectors (still restricted to int type) are hoisted before the comparison. A span of keys and values are passed to Sort, which will order the values based on the corresponding order of keys.

public static T[] ToOrderedByArray<T>(this IEnumerable<T> source, Func<T, int> keySelector)
{
    var buffer = source.ToArray();
    var keys = buffer.Select(keySelector).ToArray();
    keys.AsSpan().Sort(buffer.AsSpan());
    return buffer;
}

[Benchmark(Description = "Iteration 2")]
public DataClass[] ToOrderedByArray() => _input.ToOrderedByArray(x => x.Number);

While this approach brings performance improvements regarding the execution time, it allocates slightly more as it needs to create separate array for the calculated keys.

Method	Mean	Error	StdDev	Gen0	Gen1	Allocated
'Iteration 1'	24.63 us	0.221 us	0.196 us	1.2817	-	7.92 KB
'Iteration 2'	16.55 us	0.233 us	0.218 us	1.9226	-	11.81 KB

Iteration 3

Iteration 3 tackles the generic key problem: the code does not explicitly perform the comparison because the custom comparer is removed. Instead it relies on the implementation of the Sort method to compare items. Hence, we can replace int to a generic type parameter - and apply the same generic constraints as the Sort method has.

public static TValue[] ToOrderedByArray<TKey, TValue>(this IEnumerable<TValue> source, Func<TValue, TKey> keySelector)
{
    var buffer = source.ToArray();
    var keys = buffer.Select(keySelector).ToArray();
    keys.AsSpan().Sort(buffer.AsSpan());
    return buffer;
}

While this solution does not bring performance improvements, it makes the code more generic hence more reusable.

Iteration 4

Before moving on to the next development of this method, I want to highlight an interesting point that is relevant to our discussion. All ToOrderedByArray extension methods so far returned an array. If someone calls ToArray() on these results, it incurs an extra allocation of a new array. For example: _input.ToOrderedByArray(x => x.Number).ToArray(); will require an array allocation for the sorting and an array allocation by the ToArray() call. Benchmarking the Iteration 3 solution with the additional ToArray() call shows the extra memory required for the operation:

Method	Mean	Error	StdDev	Gen0	Gen1	Allocated
'Iteration 3'	15.18 us	0.250 us	0.234 us	1.9226	-	11.81 KB
'Iteration 3 - ToArray'	17.48 us	0.211 us	0.197 us	3.2043	0.1221	19.65 KB

However, this can be easily addressed with a neat trick that is also utilized by .NET LINQ implementation. Instead of returning an array, the extension method could return an OrderedArray<T>.

public static OrderedArray<T> ToOrderedByArray<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector)
{
    var buffer = source.ToArray();
    var keys = buffer.Select(keySelector).ToArray();
    keys.AsSpan().Sort(buffer.AsSpan());
    return new OrderedArray<T>(buffer);
}

OrderedArray<T> does not exist in BCL, it is a custom type implemented as:

public class OrderedArray<T>(T[] array) : IEnumerable<T>
{
	private readonly T[] _array = array;

	public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)array).GetEnumerator();

	IEnumerator IEnumerable.GetEnumerator() => array.GetEnumerator();

	public T[] ToArray() => array;
}

It implements IEnumerable<T> so existing LINQ operators can be appended as usual, but it also implements a ToArray() method call. In case of _input.ToOrderedByArray(x => x.Number).ToArray();, the compiler will bind to this ToArray() method instead of the extension method provided by LINQ. OrderedArray<T> wraps an array returned by the Sort operation in a readonly fashion. With this knowledge, the array required for the buffer can be safely returned by the ToArray() call. OrderedArray<T> could also implement other methods to gain further efficiency.

Method	Mean	Error	StdDev	Gen0	Gen1	Allocated
'Iteration 3 - ToArray'	17.48 us	0.211 us	0.197 us	3.2043	0.1221	19.65 KB
'Iteration 4 - ToArray'	16.63 us	0.207 us	0.194 us	1.9226	-	11.84 KB

Note, that LINQ's built-in OrderBy also requires a temporary array for ordering, but implements a streaming behavior by yield returning items from the temporary buffer. Such behavior is not implemented by these examples.

Iteration 5

This iteration addresses the allocation of the temporary keys array that is required for the Span.Sort method. Instead of allocating a new TKeys[], it uses a buffer on the stack, when the number of keys are below a certain size. A keys array for collections larger than 1000 items will be still allocated on the heap.

public static OrderedArray<T> ToOrderedByArray<T>(this IEnumerable<T> source, Func<T, int> keySelector)
{
    var buffer = source.ToArray();
    Span<int> keys = buffer.Length > 1000 ? new int[buffer.Length] : stackalloc int[buffer.Length];
    for (int i = 0; i < keys.Length; i++)
        keys[i] = keySelector(buffer[i]);
    keys.Sort(buffer.AsSpan());
    return new OrderedArray<T>(buffer);
}

This overload yields real gains when used in a tight loop such as an inner loop of a group by method call: _input.GroupBy(x => x.Number % 10).Select(group => group.ToOrderedByArray(x => x.Number).ToArray()).ToList();. The stackalloc will further reduce the load on the GC too. However, a reader might notice that ToOrderedByArray lost its genericness over the key: Func<T, int> keySelector now returns an integer value. That is because stackalloc must know the size of TKey, which it cannot infer when being generic. Iteration 6 addresses this problem.

Iteration 6

Iteration 6 uses a .NET 8 feature called inline arrays. An inline array type embeds an array into the memory representation of the type. It can do this by having a fixed size on the number of items. For example, a LimitedKeys<T> can embed 1000 items of the generic type argument T:

[System.Runtime.CompilerServices.InlineArray(1000)]
struct LimitedKeys<T>
{
	private T _element0;
}

Such a type can address the problems of stackalloc. The new LimitedKeys<TKey>() is still allocated on the stack and it can be still iterated using a Span<T>:

public static OrderedArray<T> ToOrderedByArray<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector)
{
    var buffer = source.ToArray();
    if (buffer.Length > 1000)
    {
        Span<TKey> keys = new TKey[buffer.Length];
        for (int i = 0; i < keys.Length; i++)
            keys[i] = keySelector(buffer[i]);
        keys.Sort(buffer.AsSpan());
    }
    else
    {
        var temp = new LimitedKeys<TKey>();
        Span<TKey> keys = temp;
        for (int i = 0; i < buffer.Length; i++)
            keys[i] = keySelector(buffer[i]);
        keys.Slice(0, buffer.Length).Sort(buffer.AsSpan());
    }

    return new OrderedArray<T>(buffer);
}

However, be careful when using large types for the TKey. When large value type are used for the keys, those are allocated on the stack. A user of this code may face a stack overflow exception sooner than using smaller types as the key. Another difference to notice is that the inline array is always 1000 items long, even when the source collection only contains 10 items. This means, that in such a case more memory is used on the stack compared to the stackallow approach.

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 reference types. I have presented six iterations of the ToOrderedByArray method. In each iteration, I have focused on improving the execution time or the allocated memory. The final benchmarks using 1000 items:

Method	Mean	Error	StdDev	Gen0	Gen1	Allocated
'Iteration 1'	24.63 us	0.221 us	0.196 us	1.2817	-	7.92 KB
'Iteration 2'	16.55 us	0.233 us	0.218 us	1.9226	-	11.81 KB
'Iteration 3'	15.18 us	0.250 us	0.234 us	1.9226	-	11.81 KB
'Iteration 3 - ToArray'	17.48 us	0.211 us	0.197 us	3.2043	0.1221	19.65 KB
'Iteration 4'	16.69 us	0.157 us	0.131 us	1.9226	-	11.84 KB
'Iteration 4 - ToArray'	16.63 us	0.207 us	0.194 us	1.9226	-	11.84 KB
'Iteration 5'	18.38 us	0.247 us	0.219 us	1.2817	-	7.86 KB
'Iteration 6'	16.69 us	0.262 us	0.233 us	1.2817	-	7.86 KB

The results show that the Iteration 6 solution is one of the fastest and the most memory-efficient among all the methods. It uses inlined arrays to avoid heap allocations and span sorting to avoid comparers. However, it also has some limitations, such as requiring a fixed size for the keys and being sensitive to the size of the key type.

The same performance measurements on an input source of 50 items shows a 15% execution time improvement between LinqOrderBy and Iteration 6 while also reducing memory allocations by 3 times.

Method	Mean	Error	StdDev	Gen0	Allocated
LinqOrderComparer	1,570.7 ns	11.79 ns	10.45 ns	0.1984	1248 B
LinqOrderComparerable	1,983.7 ns	28.02 ns	26.21 ns	0.1984	1248 B
LinqOrderBy	684.8 ns	5.37 ns	5.03 ns	0.2346	1472 B
'Iteration 1'	683.2 ns	5.97 ns	5.59 ns	0.0811	512 B
'Iteration 2'	602.2 ns	5.00 ns	4.43 ns	0.1106	696 B
'Iteration 3'	571.6 ns	6.67 ns	6.24 ns	0.1106	696 B
'Iteration 4'	563.0 ns	6.40 ns	5.99 ns	0.1154	728 B
'Iteration 5'	645.2 ns	4.85 ns	4.30 ns	0.0725	456 B
'Iteration 6'	575.8 ns	7.65 ns	6.78 ns	0.0725	456 B

In summary, I have demonstrated that it is possible to create a LINQ extension method that implements an unstable sort, and that it can have some performance advantages over the built-in OrderBy method, especially for small collections of reference types. However, this also comes with some trade-offs, such as losing stability and generality. Therefore, one should carefully consider the context and the data before choosing a sorting method.