In this article, we’ll examine different techniques to check whether or not a list is in order in C#. We’ll begin by examining several techniques, including parallel processing. Finally, we’ll run a series of benchmarks to help us choose which option fits best in our use case.
So, let’s begin!
Initial Setup
Before we start examining our different methodologies, we need to have some data to work with, so let’s define a simple Employee record to work with:
public record Employee(string Name, DateTime BirthDate, double Salary) : IComparable<Employee>
{
public int CompareTo(Employee? other)
=> BirthDate.CompareTo(other?.BirthDate);
}
Our Employee has 3 properties: Name, BirthDate, and Salary. We also implement the IComparable<Employee> interface, sorting our employees by BirthDate.
Next, let’s define a list of employees to use in exercising our methods:
List<Employee> employees = [
new Employee("Jack", new DateTime(1998, 11, 1), 3_000),
new Employee("Danniel", new DateTime(2000, 3, 2), 2_500),
new Employee("Maria", new DateTime(2001, 5, 23), 4_300),
new Employee("Angel", new DateTime(2001, 7, 14), 1_900)
];
Lastly, let’s define a static ListOrderValidators class to contain our different implementations:
public static class ListOrderValidators {}
One thing that is important to note. In each of our methods, we define “sorted” as a list being in ascending order.
Methods to Check List Order Using Loops
In this section, we’ll explore several techniques leveraging for/while loops to determine if a list is ordered.
Check List Order Using a Standard For Loop
First, let’s take a look at one of the simplest approaches, using a for loop to iterate the entire list:
public static bool IsOrderedUsingForLoop<T>(List<T> list, IComparer<T>? comparer = default)
{
if (list.Count <= 1)
return true;
comparer ??= Comparer<T>.Default;
for (var i = 1; i < list.Count; i++)
{
if (comparer.Compare(list[i - 1], list[i]) > 0)
return false;
}
return true;
}
As we will see with most of our methods, we pass in a List<T> and the IComparer<T> we wish to use to define our sort definition. The second thing we do is check the count of items in the list. If the list is empty or a single item we consider it “sorted” and simply return true.
Now, let’s look at the code. As we already mentioned, we are allowing for a user defined IComparer<T> to be provided. In the absence of a caller-provided comparer, we use the default comparer for the type. Now with our comparer in hand, we simply iterate the list, starting at the second element. For each iteration we check the current element to the previous in the list to ensure they are properly ordered.
Overall, this method is simple and straightforward. It has an O(N) (linear) runtime and thus also scales fairly well as our list size increases.
Check List Order Using Spans With For Loop
This second method is very similar to our first method, however now we are using Span<T> to squeeze out a little more performance. For a deep dive on Span<T> and how it can help improve our code performance, check out our article “How to Use Span in C# to Improve Application Performance“:
public static bool IsOrderedUsingForLoopWithSpan<T>(List<T> list, IComparer<T>? comparer = default)
{
if (list.Count <= 1)
return true;
comparer ??= Comparer<T>.Default;
var span = CollectionsMarshal.AsSpan(list);
for (var i = 1; i < span.Length; i++)
{
if (comparer.Compare(span[i - 1], span[i]) > 0)
return false;
}
return true;
}
After our initial checks and retrieval of the comparer, we next take a Span over our list using CollectionsMarshall.AsSpan() which comes from the System.Runtime.InteropServices namespace. After that, the code is identical to our first method. We iterate over our span checking if every two consecutive items are in the correct order.
Comparison Using Span.Sort
In our third method, rather than comparing consecutive elements to each other, we will first copy the elements to a new collection. Next, we sort the new collection, and finally compare the two collections:
public static bool IsOrderedUsingSpanSort<T>(List<T> list, IComparer<T>? comparer = default)
{
if (list.Count <= 1)
return true;
T[]? array = null;
try
{
comparer ??= Comparer<T>.Default;
var listSpan = CollectionsMarshal.AsSpan(list);
var length = listSpan.Length;
array = ArrayPool<T>.Shared.Rent(length);
var arraySpan = array.AsSpan(0, length);
listSpan.CopyTo(arraySpan);
arraySpan.Sort(comparer);
for (var i = 0; i < length; i++)
{
if (comparer.Compare(listSpan[i], arraySpan[i]) != 0)
return false;
}
return true;
}
finally
{
if (array is not null)
ArrayPool<T>.Shared.Return(array);
}
}
As with our previous method, we again use CollectionsMarshal.AsSpan() to get a span over our list. Next, we rent an array from the ArrayPool, and take a span over it. Following that, we copy our list to the span.
The last step in the setup is to sort the span. Finally, we iterate over the two collections comparing each element for equality. Our last step is to ensure that we return the rented array to the ArrayPool, which we handle via a finally block.
Check List Order Using Enumerator
The last method of this section involves the usage of an IEnumerator<> to iterate through the collection:
public static bool IsOrderedUsingEnumerator<T>(IList<T> list, IComparer<T>? comparer = default)
{
if (list.Count <= 1)
return true;
comparer ??= Comparer<T>.Default;
var previous = list[0];
using var enumerator = list.GetEnumerator();
enumerator.MoveNext();
while (enumerator.MoveNext())
{
var current = enumerator.Current;
if (comparer.Compare(previous, current) > 0)
return false;
previous = current;
}
return true;
}
First, we define a previous variable which points to the first element of our list. Following that we create the enumerator via a call to GerEnumerator(). Since we want to start our comparison at the second element of the list, we perform an initial MoveNext() before we begin to iterate our collection via the enumerator.
Within the while loop we first move to the next element in the collection and store that as the current element. Then we compare the current to the previous to ensure they are in the proper order. Finally, before beginning the next iteration, we set previous to current and loop.
Check the List Order Using LINQ
In this section, we’ll examine some techniques using LINQ to determine if a list is ordered. While they may not be the most efficient methods, they often produce simpler and more readable code. So let’s dive in.
Check List Order Using Order and Enumerators
Our first method in this section is a bit of a hybrid. We use Enumerable.Order() to get IOrderedEnumerable<T> of our collection, and then iterate it using an enumerator:
public static bool IsOrderedUsingLinqWithOrder<T>(IList<T> list, IComparer<T>? comparer = default)
{
if (list.Count <= 1)
return true;
comparer ??= Comparer<T>.Default;
var orderedList = list.Order(comparer);
var index = 0;
using var enumerator = orderedList.GetEnumerator();
while (enumerator.MoveNext() && index < list.Count)
{
if (comparer.Compare(list[index++], enumerator.Current) != 0)
return false;
}
return true;
}
Here, unlike in our previous example involving an enumerator, we don’t need to worry about a current and previous value. We iterate the ordered enumerable, comparing the current element to the element in our original list at the same position. If the elements are not equal, i.e. their comparison is not 0, then we know the list is not ordered.
Check List Order Using LINQ’s Order and SequenceEqual Methods
Let’s start using the LINQ Order() method, which allows us to enumerate elements of a sequence in ascending order:
public static bool IsOrderedUsingLinqWithSequenceEqual<T>(IList<T> list, IComparer<T>? comparer = default,
IEqualityComparer<T>? equalityComparer = default)
{
if (list.Count <= 1)
return true;
comparer ??= Comparer<T>.Default;
equalityComparer ??= EqualityComparer<T>.Default;
var orderedList = list.Order(comparer);
return list.SequenceEqual(orderedList, equalityComparer);
}
One notable difference in this method is the need for a separate IEqualityComparer<T>. This is because SequenceEqual() uses this comparer when determining if two elements are equal. So in addition to getting a comparer object, we also ensure that we have an equality comparer.
Next, we create an IOrderedEnumerable<T> using the Order() method, passing in our IComparer<T>. Lastly, we call SequenceEqual() to compare our original list against the ordered one element by element.
Check List Order Using Zip Method
Another interesting method we can use for checking if a list is ordered is the Zip() method, which allows us to “zip” two collections together:
public static bool IsOrderedUsingLinqWithZip<T>(IList<T> list, IComparer<T>? comparer = default)
{
if (list.Count <= 1)
return true;
comparer ??= Comparer<T>.Default;
return !list
.Zip(list.Skip(1), (a, b) => comparer.Compare(a, b) <= 0)
.Contains(false);
}
Here, in the Zip() method, we use 2 collections – the original list and a new one where only the first element is omitted. We then “zip” or merge together the collections into a new one, where the elements are defined as the comparison between the elements of the source lists. Finally, using LINQ Contains() we search the zipped collection for false, which indicates that our list is not ordered.
Check the List Order Using the Task Parallel Library
For our final set of methods, let’s see how we can use the Task Parallel Library to enhance the performance of list order verification. This library allows for easy parallelization of for loops, which can help speed the processing of lists of data. This can be especially helpful when dealing with larger lists and collections.
Check List Order Using Parallel.For
The Parallel.For() method from the Task Parallel Library allows us to run iterations of a for loop in parallel, potentially speeding up our list processing. Like with a traditional for loop, the Parallel.For allows us to monitor and break from the loop early if we need to, allowing us the same fine-grained control we are used to with traditional loops.
Let’s define the IsOrderedUsingParallelFor() method:
public static bool IsOrderedUsingParallelFor<T>(IList<T> list, IComparer<T>? comparer = default)
{
if (list.Count <= 1)
return true;
comparer ??= Comparer<T>.Default;
var result = Parallel.For(1, list.Count, (index, state) =>
{
if (!state.IsStopped && comparer.Compare(list[index - 1], list[index]) > 0)
state.Stop();
});
return result.IsCompleted;
}
Parallel.For() has several overloads, but we are calling the one that takes 3 parameters: an inclusive start index, an exclusive end index, and an Action<int, ParallelLoopState>. Just like our simple for loop case, we start our iteration from the second element (index 1), and compare each element in the collection to the previous one. Note that we also check the loop state to ensure we have not hit a stop condition in another thread.
If we find any unordered elements, we call state.Stop(), signaling to the parallel loop to prematurely exit and stop further processing. Lastly, we return result.IsCompleted which will be true if all elements of the list have been examined, indicating that the list is ordered. If state.Stop() is called in any of the worker threads, IsCompleted will be false.
Check List Order Using Parallel.For and Partitions
Similar to our previous example, we are once again calling Paralell.For() but with some additional complexity involving partitioning our collection into chunks. We then process the chunks in parallel. This can help to increase performance through better data localization. To help compute the optimal chunk size, we use the Environment.ProcessorCount to determine the number of available logical processors for our current process:
public static bool IsOrderedUsingParallelForPartitioned<T>(List<T> list, IComparer<T>? comparer = default)
{
const int minPartitionLength = 4;
if (list.Count <= 1)
return true;
comparer ??= Comparer<T>.Default;
var length = list.Count;
var maxPartitions = 1 + (length - 1) / minPartitionLength;
var partitions = Math.Min(Environment.ProcessorCount, maxPartitions);
if (partitions == 1)
return IsOrderedUsingForLoopWithSpan(list, comparer);
var partitionSize = 1 + (length - 1) / partitions;
var options = new ParallelOptions {MaxDegreeOfParallelism = partitions};
var result = Parallel.For(0, partitions, options,
(partitionIndex, state) =>
{
var low = partitionIndex * partitionSize;
var high = Math.Min(length, low + partitionSize + 1) - 1;
for (var i = low; i < high && !state.IsStopped; i++)
{
if (comparer.Compare(list[i], list[i + 1]) > 0)
state.Stop();
}
});
return result.IsCompleted;
}
First, we calculate the maximum number of partitions we would want based on a simple calculation that ensures we have at least 1 partition and also indicates that the minimum number of elements in a partition should be 4. Following this calculation we compute the actual number of partitions based on the minimum between our calculated maxPartitions and the processor count.
Once we have our partition count settled we make one more check whether the number of partitions is 1. In the case of a single partition we simply call into our iterative IsOrderedUsingForLoopWithSpan() method.
Now that we have established that we have at least 2 partitions, we calculate the length of the partitions based on the collection length and our partition count. Following this we construct a ParalellOptions object to define our maximum desired degree of parallelism.
Calling Paralell.For
With all of the setup done, we are now ready to call Paralell.For(). This time we are using the four-parameter overload which takes a fromInclusive index, a toInclusive index, a ParallelOptions object, and finally a body which is an Action<int, ParallelLoopState>. Since we are partitioning our collection, we define our indexes from 0 to our partition count. We pass in our options object which sets the max degree of parallelism, and then finally we define our body.
We start by calculating our starting index (low) based on which partition we are processing. Next, we define our ending index (high) based on the minimum between our actual collection length and a computation based on our starting index and partition size. Note that we also are subtracting one from this value (the importance of which will become apparent as we examine the next part of the body).
With our indexes calculated, we can now loop over our collection, starting at our low value and ending at our high value. Inside the for loop, we compare the value of list[i] with list[i+1] (which is why we initially subtracted 1 from our high value). If we find an unordered element, we call state.Stop() to break out of the loop and indicate to all other parallel loops to stop.
Lastly, just as we did in our simple Parallel.For() implementation, we return result.IsCompleted to indicate whether the list is ordered or not.
Combining Parallel.For and Spans
For this last method, we will combine the idea of parallel processing on partitioned data, but within our Action lambda, we will take a span over the partition:
public static bool IsOrderedUsingParallelForPartitionedWithSpans<T>(
List<T> list, IComparer<T>? comparer = default)
{
// ...Removed for brevity...
var result = Parallel.For(0, partitions, options,
(partitionIndex, state) =>
{
var low = partitionIndex * partitionSize;
if (low >= length)
return;
var high = Math.Min(length, low + partitionSize + 1);
var span = CollectionsMarshal.AsSpan(list)[low..high];
for (var i = 0; i < span.Length - 1 && !state.IsStopped; i++)
{
if (comparer.Compare(span[i], span[i + 1]) > 0)
state.Stop();
}
});
return result.IsCompleted;
}
The initial setup for this method is the same as the previous one, so for brevity, we have removed it. Our main focus here is the lambda body of the Paralell.For() where we are taking a span over the collection and operating on it.
Our index computation is almost the same as the previous method with two minor exceptions. First, we check if our low index is beyond the array length, and if so, we simply return. Due to the nature of our partition calculation, it is possible to have an “extra” partition due to rounding. The second exception is that we don’t subtract 1 from our high index, since we use the low and high to slice our span. Following the computations, we use CollectionMarshal.AsSpan() to get a span over our list and slice it to the size of our partition.
Next, we begin looping over the span. Notice here that we are starting from 0 and looping until the end of the span save 1. The span itself takes care of computing the offset based on the slice we created. Inside the loop we perform our comparison of sequential items, calling state.Stop() if we find unordered items. Lastly, as before, we return result.IsCompleted.
Comparison Between the Methods Using Performance Benchmarks
Now, let’s see how all the methods we examined stack up against each other in terms of speed. We’ll run performance benchmark tests to compare how quickly they can check if a list is in the right order.
For this purpose, we’ll use the BenchmarkDotnet library to run performance benchmarks using all the different methods. We’re going to test input lists having 10,000; 25,000; and 1,000,000 elements respectively.
With that said, let’s see the results:
| Method | Length | Mean | Allocated | |---------------------------------------------- |-------- |--------------:|----------:|- | IsOrderedUsingSpans | 10000 | 4.903 us | - | | IsOrderedUsingParallelForPartitionedWithSpans | 10000 | 8.778 us | 3870 B | | IsOrderedUsingForLoop | 10000 | 9.823 us | - | | IsOrderedUsingParallelForPartitioned | 10000 | 10.506 us | 4006 B | | IsOrderedUsingEnumerator | 10000 | 18.279 us | 40 B | | IsOrderedUsingParallelFor | 10000 | 21.752 us | 5498 B | | IsOrderedUsingSpanSort | 10000 | 56.526 us | - | | IsOrderedUsingLinqWithOrder | 10000 | 73.764 us | 40112 B | | IsOrderedUsingLinqWithZip | 10000 | 79.241 us | 272 B | | IsOrderedUsingLinqWithSequenceEqual | 10000 | 92.499 us | 40152 B | | | | | | | IsOrderedUsingSpans | 25000 | 12.757 us | - | | IsOrderedUsingParallelForPartitionedWithSpans | 25000 | 13.564 us | 4153 B | | IsOrderedUsingParallelForPartitioned | 25000 | 16.702 us | 4233 B | | IsOrderedUsingForLoop | 25000 | 25.091 us | - | | IsOrderedUsingParallelFor | 25000 | 34.593 us | 5279 B | | IsOrderedUsingEnumerator | 25000 | 47.508 us | 40 B | | IsOrderedUsingSpanSort | 25000 | 143.391 us | - | | IsOrderedUsingLinqWithZip | 25000 | 206.634 us | 272 B | | IsOrderedUsingLinqWithOrder | 25000 | 224.838 us | 100123 B | | IsOrderedUsingLinqWithSequenceEqual | 25000 | 265.513 us | 100163 B | | | | | | | IsOrderedUsingParallelForPartitionedWithSpans | 1000000 | 337.040 us | 5010 B | | IsOrderedUsingParallelForPartitioned | 1000000 | 421.753 us | 5135 B | | IsOrderedUsingSpans | 1000000 | 602.323 us | - | | IsOrderedUsingParallelFor | 1000000 | 744.821 us | 5488 B | | IsOrderedUsingForLoop | 1000000 | 1,129.064 us | 1 B | | IsOrderedUsingEnumerator | 1000000 | 2,004.603 us | 41 B | | IsOrderedUsingSpanSort | 1000000 | 7,802.513 us | 12 B | | IsOrderedUsingLinqWithZip | 1000000 | 9,308.523 us | 278 B | | IsOrderedUsingLinqWithOrder | 1000000 | 10,472.187 us | 4000235 B | | IsOrderedUsingLinqWithSequenceEqual | 1000000 | 12,084.804 us | 4000275 B |
Based on our benchmarks, for smaller lists of 25,000 elements or less, IsOrderedUsingSpans() is our best performer. Around the 25,000 element mark, however, IsOrderedUsingParallelForPartitionedWithSpans() begins to close the gap with the standard iteration method. As our list size increases, IsOrderedUsingParallelForPartitionedWithSpans() is the standout winner. While the setup is a bit more complicated, if we know we are dealing with large lists, the performance gain is worth the complication.
Our benchmarks clearly show that there is some overhead related to running the Parallel.For() options, which is why it is not recommended to use these techniques unless we know we will be dealing with larger collections. An excellent approach would be to create a hybrid method, which chooses between a standard for loop, or the Parallel.For() based on the list size.
As with any approach, we need to consider both performance, scalability and code maintenance. If this is an operation that we only perform once a day in our application, then maybe just opting for the straightforward for loop with a span will be sufficient. If we are processing large collections several times a minute, then our application will most likely benefit from exploring a more parallel approach.
Conclusion
Each of the methods has its own pros and cons. It is up to us as developers to consider our use case and to choose the option that fits best with our problem at hand.
