Hello, I am Laszlo

IsSorted using SIMD in .NET

07/11/2026 | 6 minutes to read

Sorting a set or an array is a relatively expensive operation. The costs of sorting typically increase non-linearly with the input size. Therefore, in certain cases, it can be beneficial to check if an array is already sorted before attempting to sort it.

Note: Different sorting algorithms handle sorted or 'nearly sorted' collections with varying degrees of efficiency.

For perspective, sorting an already sorted integer array with a million elements using Array.Sort in .NET takes 5,180.9 us on my machine. In contrast, validating if the same array is sorted takes only 119.0 us. For applications where most input arrays are expected to be sorted, validating sorted-ness first can be a worthwhile optimization.

Similarly, an operation like binary search might want to validate the precondition of the input array being sorted.

Naive Implementation

To validate if an integer array is sorted a developer can iterate the elements and check for elements if the previous element is not larger. If it is larger, return false without checking the rest of the array. Such an algorithm is shown below:

public bool IsSorted1(int[] input)
{
    for (int i = 1; i < input.Length; i++)
    {
        if (input[i] < input[i - 1])
            return false;
    }
    return true;
}

Single Instruction Multiple Data

Single Instruction Multiple Data or SIMD operations allow processing multiple data elements with a single CPU instruction. Most modern CPUs (x64, ARM) support SIMD through dedicated instruction sets.

A .NET application can either:

• Directly use these instruction sets (ensuring platform compatibility)
• Use higher-level APIs that abstract platform specifics

The Vector<T> type provides this abstraction. When SIMD instructions like SSE, AVX2, or AVX10.2 are available on the executing platform, Vector<T> leverages those. Otherwise, it falls back to non-vectorized instructions.

On the machine used for this post, the AVX2 instruction set is available. It supports 256-bit vector registers, which can hold:

• 8 × 4-byte integers
• 4 × 8-byte doubles
• 32 individual bytes
• etc.

Let's convert the above algorithm to leverage SIMD operations. Checking if an array is sorted means comparing the current element with the previous one. With vectors, two vectors can be compared with GreaterThan:

Vector.GreaterThan(left, right)

This method compares two vectors element by element and returns a third vector containing 'all-bits-set' for the element where a left element is greater than the corresponding element of right. Its documentation says A vector whose elements are all-bits-set or zero, depending on if which of the corresponding elements in left and right were greater.

With AVX2 8 integers can be loaded into a vector, which means that 8 neighboring integers could be compared at a time. To do this fill one vector with the input from the current position, then fill another vector with 1 offset to the current position. For example, in case of an array of [0, 1, 2, 3, 4, -1, 6, 7, 8, 9, ... ] the two initial vectors would be

[0, 1, 2, 3, 4, -1, 6, 7]
[1, 2, 3, 4, -1, 5, 7, 8]

Compare the vectors and determine if the result vector is a Zero vector (where all elements are 0). If not, the array is not sorted. In the above case at index 4, value 4 from the first vector is higher than -1 from the second vector, which results:

[0, 0, 0, 0, -1, 0, 0, 0]

The main loop of the algorithm can be written using Vector<T> types as:

vCurrent = Vector.LoadUnsafe(ref input[i]);
vCurrent1 = Vector.LoadUnsafe(ref input[i + 1]);
comparison = Vector.GreaterThan(vCurrent, vCurrent1);
if (comparison != Vector<int>.Zero)
    return false;

However, working with Vector<T>s requires additional care. Vector<T>s cannot be loaded from sources shorter than the vector length; 8 integers with AVX2. An input might be less than a vector length, e.g. an input with only a single element. When the length of the array is less than a Vector<T>'s supported length (Vector<int>.Count) the IsSorted2 method can fallback using the IsSorted1 method.

Similarly, when the above code is executed in a loop, the remaining unprocessed elements of the input array might be less than the supported length. Fortunately, we can do a trick here by loading more elements than needed. Taking the last vector sized segment of the input: this means some elements might be compared twice, but there is no need to fall back to non-vectorized code, while the duplicate comparisons won't change the result of this algorithm.

Putting all this together the IsSorted2 method can be implemented as:

public bool IsSorted2(int[] input)
{
    if (input.Length < Vector<int>.Count + 1)
        return IsSorted1(input);

    int i = 0;
    Vector<int> vCurrent;
    Vector<int> vCurrent1;
    Vector<int> comparison;
    for (; i < input.Length - Vector<int>.Count - 1; i += Vector<int>.Count)
    {
        vCurrent = Vector.LoadUnsafe(ref input[i]);
        vCurrent1 = Vector.LoadUnsafe(ref input[i + 1]);
        comparison = Vector.GreaterThan(vCurrent, vCurrent1);
        if (comparison != Vector<int>.Zero)
            return false;
    }

    i = input.Length - Vector<int>.Count - 1;
    vCurrent = Vector.LoadUnsafe(ref input[i]);
    vCurrent1 = Vector.LoadUnsafe(ref input[i + 1]);
    comparison = Vector.GreaterThan(vCurrent, vCurrent1);
    return comparison == Vector<int>.Zero;
}

Performance

The benefit of writing longer and more complicated code is performance. Let's compare IsSorted1 and IsSorted2 methods with an int[] of 1 million elements. This benchmark uses .NET 10 RC1 release on Windows 11 version 24H2. The benchmarking machine supports AVX2 instruction set.

The performance characteristics depend heavily on the input array. We'll test two scenarios:

1. A completely sorted array
2. A nearly sorted array with an unsorted value at index 7

Results using BenchmarkDotNet for the sorted array:

| Method    | Mean     | Error   | StdDev  | Ratio |
|---------- |---------:|--------:|--------:|------:|
| IsSorted1 | 367.6 us | 2.25 us | 1.99 us |  1.00 |
| IsSorted2 | 116.1 us | 2.21 us | 2.64 us |  0.32 |

The sorted case is more than 3 times faster when using SIMD approach. Normally, it would expect an 8-time improvement, but modern CPUs are good at branch predictions, making it somewhat more competitive.

With an unsorted array the 7th element is the outlier.

| Method    | Mean      | Error     | StdDev    | Median    | Ratio | RatioSD |
|---------- |----------:|----------:|----------:|----------:|------:|--------:|
| IsSorted1 | 2.4956 ns | 0.0851 ns | 0.0796 ns | 2.4895 ns | 1.001 |    0.04 |
| IsSorted2 | 0.0057 ns | 0.0075 ns | 0.0070 ns | 0.0037 ns | 0.002 |    0.00 |

The results in this case favor the vectorized approach.

Conclusion

Using SIMD operations through .NET's Vector<T> type provides significant performance benefits for checking if an array is sorted. While the code is more complex than the naive implementation, the performance gains are substantial:

• For sorted arrays, the SIMD implementation is over 3x faster
• For arrays with early unsorted elements, the SIMD version shows even greater improvements
• The implementation gracefully handles edge cases by falling back to the naive approach when needed

This example demonstrates how modern CPU features like AVX2 can be leveraged through .NET's hardware intrinsics to achieve meaningful performance improvements. While not every application needs this level of optimization, scenarios involving large arrays or frequent sorted-ness checks can benefit significantly from this approach.

Remember that such optimizations should be carefully considered based on your specific use case, as the added code complexity should be justified by measurable performance benefits in your application.