In this article, we will explore different techniques for sorting a list. A common task we face as developers is the need to sort a collection of data. The C# language provides us with a variety of ways in which we can accomplish this task. To help us have a better understanding of the available options, we will walk through several examples together.
Along with exploring different techniques for sorting a list, we will also implement our own custom MySortedList class which will allow us to maintain a list of data in a sorted fashion.
With that in mind, let’s dive into some code.
Setting Up Our Example Code
First, let’s create a simple record that we can use to explore the different options and techniques for sorting a list:
public sealed record Product(string ProductName, string Category, decimal Price)
{
public Guid Id { get; init; } = Guid.NewGuid();
}
Second, let’s generate some sample data, which we can use to demonstrate the different techniques for sorting a list:
new Product?[]
{
new("Gorgeous Fish", "Games", 103.07m) { Id = Guid.Parse("f0569e86-bfad-6f3a-b74d-2555175dcc6e") },
new("Tasty Cheese", "Clothing", 134.74m) { Id = Guid.Parse("4af80b60-3e17-1dfd-8462-c009ca918154") },
null,
new("Handcrafted Hat", "Books", 38.09m) { Id = Guid.Parse("c7b30b28-db07-f2ae-70dc-9505096e676b") },
new("Practical Chicken", "Electronics", 126.06m) { Id = Guid.Parse("d6fee4b9-8767-851a-b386-a8af727663a7") },
new("Generic Car", "Games", 75.18m) { Id = Guid.Parse("c65100fd-e49f-f5e0-0e71-052d7eefe9b3") }
};
As a side note, we have generated this data using the Bogus NuGet package. To learn more about Bogus and how it can be used to generate “realistic” testing data, be sure to check out our article on the topic.
Formatted nicely, our unsorted data looks like this:
Gorgeous Fish Games $103.07 f0569e86-bfad-6f3a-b74d-2555175dcc6e Tasty Cheese Clothing $134.74 4af80b60-3e17-1dfd-8462-c009ca918154 NULL NULL $0.00 00000000-0000-0000-0000-000000000000 Handcrafted Hat Books $38.09 c7b30b28-db07-f2ae-70dc-9505096e676b Practical Chicken Electronics $126.06 d6fee4b9-8767-851a-b386-a8af727663a7 Generic Car Games $75.18 c65100fd-e49f-f5e0-0e71-052d7eefe9b3
So let’s dive in and begin exploring the different options available to us for sorting.
IComparable<T> Interface for Sorting a List in C#
The IComparable<T> interface provides a mechanism for defining the default comparison behavior of a class. When defining a new class, that we wish to be sortable, we implement this interface to define the default sorting order.
The IComparable<T> interface defines a single method that we need to implement:
public int CompareTo (T? other)
The value returned indicates the relative positioning of the two objects within the desired sort order:
< 0– the instance precedesotherin the sort order0– the instance is in the same position asotherin the sort order> 0– the instance followsotherin the sort order
When implementing IComparable<T> we should also override Equals() as well as the comparison operators <, <=, >, >= to maintain consistency with the results of CompareTo(). When overriding Equals() it is good practice to also override the equality and inequality operators == and !=.
For more information concerning overriding Equals() and operator overloading, you can check out our article covering that topic.
For simplicity’s sake and to keep the focus of our article on sorting, we are using a record rather than a class, which handles the equality overriding for us. You can read more about the record type in our article here.
Implementing IComparable<T>
Now, let’s take a look at implementing the IComparable<T> interface on our Product record. First, we will change our record signature to include the IComparable<T> interface, along with the non-generic IComparable interface:
public sealed record Product(string ProductName, string Category, decimal Price) : IComparable<Product>, IComparable
First, let’s take a look at our IComparable<Product> implementation. We will focus on sorting Productsbased primarily on the ProductName and only secondarily sort based on the Price:
public int CompareTo(Product? other)
{
if (ReferenceEquals(this, other)) return 0;
if (other is null) return 1;
var nameComparison = string.Compare(ProductName, other.ProductName,
StringComparison.OrdinalIgnoreCase);
return nameComparison != 0 ? nameComparison : Price.CompareTo(other.Price);
}
The first thing we do on line #3 is to perform a reference comparison to check if we are comparing the same object with itself. If that is the case, we return 0, indicating that the objects occur in the same position within the sort order. Note that we did not say that a return value of 0 indicates equality, only their relative positioning within the sort order. Equal objects must return 0, but it is possible, based on how we are sorting, to have two unequal objects that still share the same position in relation to their sort order.
Second, on line #4 we check whether other is null. In the case of it being null, we return 1 indicating that our current object is larger than the null object.
Third, on line #6 we compare the ProductName of the two objects. Since we have already verified that they are not the same object and that other is not null, we can safely make this comparison.
This leads us to the last line, #8, where we check to see if the ProductName has the same sort-order positioning. If it does, then we compare the Price as a way of determining which object should be first in the sort order.
IComparable<T> Implementation In Action
Now let’s see what happens when we sort our Product collection:
var productList = new List<Product?>(products); productList.Sort();
Let’s inspect the result:
NULL NULL $0.00 00000000-0000-0000-0000-000000000000 Generic Car Games $75.18 c65100fd-e49f-f5e0-0e71-052d7eefe9b3 Gorgeous Fish Games $103.07 f0569e86-bfad-6f3a-b74d-2555175dcc6e Handcrafted Hat Books $38.09 c7b30b28-db07-f2ae-70dc-9505096e676b Practical Chicken Electronics $126.06 d6fee4b9-8767-851a-b386-a8af727663a7 Tasty Cheese Clothing $134.74 4af80b60-3e17-1dfd-8462-c009ca918154
IComparer<T> Interface for Sorting a List in C#
Sometimes when we are sorting, we do not want to follow the default sort defined for a given type T. The IComparer<T> interface is one of the techniques we can use for sorting a list according to our own desired sort order. It allows an implementing type to define a Compare() method that can be used to sort objects of type T. The Compare() method signature is very similar to the CompareTo() method that we looked at with the IComparable<T> interface:
public int Compare (T? a, T? b)
Just like the CompareTo() method, the value returned indicates the relative positioning of the two objects within the desired sort order:
< 0–aprecedesbin the sort order0–ais in the same position asbin the sort order> 0–afollowsbin the sort order
A common use case for the IComparer<T> is to define a custom comparer to use for sorting a collection differently than the default ordering defined by the object. For example, the default sort ordering of our Product object is based on the natural ordering of the ProductName. We can override that behavior when sorting a collection by defining an IComparer<Product> that sorts based on the price.
Implementing IComparer<T> for Custom Sorting
Let’s take a look at it in action. We’ll start with our class definition:
public sealed class ProductPriceIComparer : IComparer<Product?>
The only thing left to do is to implement the Compare(Product? x, Product? y) method:
public int Compare(Product? a, Product? b)
{
if (ReferenceEquals(a, b)) return 0;
if (a is null) return -1;
if (b is null) return 1;
var priceComparison = a.Price.CompareTo(b.Price);
return priceComparison != 0 ? priceComparison :
string.Compare(a.ProductName, b.ProductName, StringComparison.OrdinalIgnoreCase);
}
The code looks very similar to the CompareTo() method that we defined earlier, with one very notable difference, the number of arguments. CompareTo() is a member of the Product class and so only takes a single argument, namely the other Product to compare with the current Product. When we implement the ICompare<T> interface, the Compare() method performs the comparison with two provided Product objects.
First, on line #3, we check whether the two objects are the same object. In that case, we just return 0. Next, on line #4, we check to see if a is null. If it is, then we return -1 indicating that a comes before b in the sorting order. On line #5 we also check whether b is null and if it is, we return 1 to indicate that b comes before a in the sorting order.
The major difference between our earlier CompareTo() and this Compare() is found on lines 7 and 9. In our CompareTo() method, we first performed a comparison on the ProductName and then, only if the ProductName was equal regarding sort order, did we compare the Price. In this case, we are checking the Price first, as our goal is to order Products according to Price rather than ProductName.
IComparer<T> Implementation in Action
Let’s see our collection when we sort it using the ProductPriceIComparer:
var productList = new List<Product?>(products); productList.Sort(new ProductPriceIComparer());
And, let’s check the result:
NULL NULL $0.00 00000000-0000-0000-0000-000000000000 Handcrafted Hat Books $38.09 c7b30b28-db07-f2ae-70dc-9505096e676b Generic Car Games $75.18 c65100fd-e49f-f5e0-0e71-052d7eefe9b3 Gorgeous Fish Games $103.07 f0569e86-bfad-6f3a-b74d-2555175dcc6e Practical Chicken Electronics $126.06 d6fee4b9-8767-851a-b386-a8af727663a7 Tasty Cheese Clothing $134.74 4af80b60-3e17-1dfd-8462-c009ca918154
The Comparer<T> Abstract Class
We have already looked at the IComparer<T> interface, so now let’s take a look at the abstract class Comparer<T> which is an abstract base class that implements the IComparer<T> interface.
Given the choice between implementing the interface and deriving from the base class, deriving from Comparer<T> is the recommended approach by Microsoft. The remarks section of the documentation for IComparer<T> explains why we should prefer deriving from Comparer<T> over implementing the interface.
Deriving from Comparer<T>
So let’s take a look at creating a custom comparer to sort our Product items by Id via the Comparer<T>:
public sealed class ProductIdComparer : Comparer<Product?>
Since we are looking to implement a comparer for the Product class, we derive from the generic Comparer<T> class passing in Product for our generic type argument.
Next, we need to implement Compare(), just like we did when implementing the IComparer<T> interface:
public override int Compare(Product? a, Product? b)
{
// removed for brevity
return a.Id.CompareTo(b.Id);
}
For brevity, we have omitted the first three lines of the method, as they are identical to lines 3-5 in the IComparer<T> implementation. In our case, we are defining a comparison based on the Id of the Product. With this as our goal, all we need to do is return the result of the Id comparison.
One important difference to note between implementing the IComparer<T> interface and deriving from Comparer<T> is the signature of the Compare() method. When implementing the interface, we simply define a public Compare() method. When deriving from the base class, we have to override the Compare() method.
Comparer<T> Implementation in Action
Let’s take a look at our Id comparer in action:
var productList = new List<Product?>(products); productList.Sort(new ProductIdComparer());
The result:
NULL NULL $0.00 00000000-0000-0000-0000-000000000000 Tasty Cheese Clothing $134.74 4af80b60-3e17-1dfd-8462-c009ca918154 Generic Car Games $75.18 c65100fd-e49f-f5e0-0e71-052d7eefe9b3 Handcrafted Hat Books $38.09 c7b30b28-db07-f2ae-70dc-9505096e676b Practical Chicken Electronics $126.06 d6fee4b9-8767-851a-b386-a8af727663a7 Gorgeous Fish Games $103.07 f0569e86-bfad-6f3a-b74d-2555175dcc6e
Sorting With The Comparison<T> Delegate
Now, let’s take a look at the Comparison<T> delegate. This delegate is one of the techniques we can employ when sorting a list. The following signature defines it:
public delegate int Comparison<in T>(T a, T b);
Just like our other comparison methods (CompareTo() and Compare()), the Comparison<T> delegate returns an int based on the sort order of compared objects:
< 0–aprecedesbin the sort order0–ais in the same position asbin the sort order> 0–afollowsbin the sort order
To use the Comparison<T> delegate, we simply invoke the Sort() overload that accepts the delegate. We can accomplish this either by passing in a lambda function directly or by defining a method that matches the delegate signature. Let’s look at both options.
Defining Comparison<T> Delegate via a Lambda
Here we’ll invoke Sort() with a lambda that orders our Product items by Category:
var productList = new List<Product?>(products);
productList.Sort((a, b) =>
{
// object and null checks removed for brevity
var result = string.Compare(a.Category, b.Category, StringComparison.OrdinalIgnoreCase);
return result != 0 ? result : a.CompareTo(b);
});
Once again for brevity, we removed the object and null checks from the code listing, as they are identical to our earlier example. Following those checks, we perform a comparison of the Category property. If the Product instance a and b compare share the same category, we fall back to calling the default comparison (Name, followed by Price).
Now let’s take a look at the result:
NULL NULL $0.00 00000000-0000-0000-0000-000000000000 Handcrafted Hat Books $38.09 c7b30b28-db07-f2ae-70dc-9505096e676b Tasty Cheese Clothing $134.74 4af80b60-3e17-1dfd-8462-c009ca918154 Practical Chicken Electronics $126.06 d6fee4b9-8767-851a-b386-a8af727663a7 Generic Car Games $75.18 c65100fd-e49f-f5e0-0e71-052d7eefe9b3 Gorgeous Fish Games $103.07 f0569e86-bfad-6f3a-b74d-2555175dcc6e
Defining Comparison<T> Delegate via a Method
As we mentioned earlier, we can also define a method that matches the Comparison<T> delegate signature and pass that as the argument to the Sort() overload, which takes a Comparison<T>. Let’s see how this works by defining a new static DescendingCompare() method in our Product class:
public static int DescendingCompare(Product? a, Product? b) => b?.CompareTo(a) ?? -1;
This method is pretty straightforward. Our goal is to sort Products in descending order, so all we need to do is “reverse” the comparison result of the current CompareTo() implementation. We accomplish this by reversing the operands when performing the comparison. That is, instead of comparing a to b, we compare b to a. One thing to note is the return value when b is null. Because we are sorting in descending order, smaller values sort lower in the collection, and therefore if b is null we return -1.
Now let’s put it to use:
var productList = new List<Product?>(products); productList.Sort(Product.DescendingCompare);
And the results:
Tasty Cheese Clothing $134.74 4af80b60-3e17-1dfd-8462-c009ca918154 Practical Chicken Electronics $126.06 d6fee4b9-8767-851a-b386-a8af727663a7 Handcrafted Hat Books $38.09 c7b30b28-db07-f2ae-70dc-9505096e676b Gorgeous Fish Games $103.07 f0569e86-bfad-6f3a-b74d-2555175dcc6e Generic Car Games $75.18 c65100fd-e49f-f5e0-0e71-052d7eefe9b3 NULL NULL $0.00 00000000-0000-0000-0000-000000000000
Constraining the Sorting to a Range
Regarding techniques for sorting a list using the List.Sort() method, there is one additional overload that we haven’t discussed yet. This overload allows us to restrict our sorting to a specific range within the list. The method signature is as follows:
List<T>.Sort(int index, int count, IComparer<T>? comparer)
We specify the starting index via the first parameter. The second parameter specifies the number of elements that should be included in the sort, starting from the index. The last parameter, which may be null, specifies the IComparer<T> to use for performing the sort. If we pass in null, then the default comparer for type T will be used.
As expected, the range we specify must be valid for the list. If we try to pass in negatives or a range that does not fall within the bounds of the list, an ArgumentException will be thrown. Also, if we specify null for the comparer, and T does not have a default comparer defined, then an InvalidOperationException will be thrown.
Now, let’s see this overload of Sort() in action. We will sort the first 3 elements of our sample list by Price, which is handled by our previous implementation ProductPriceIComparer, and the last 3 using the default Product comparison:
var productList = new List<Product?>(products); productList.Sort(0, 3, new ProductPriceIComparer()); productList.Sort(3, 3, null);
And the results:
NULL NULL $0.00 00000000-0000-0000-0000-000000000000 Gorgeous Fish Games $103.07 f0569e86-bfad-6f3a-b74d-2555175dcc6e Tasty Cheese Clothing $134.74 4af80b60-3e17-1dfd-8462-c009ca918154 Generic Car Games $75.18 c65100fd-e49f-f5e0-0e71-052d7eefe9b3 Handcrafted Hat Books $38.09 c7b30b28-db07-f2ae-70dc-9505096e676b Practical Chicken Electronics $126.06 d6fee4b9-8767-851a-b386-a8af727663a7
Custom MySortedList<T> Implementation for Sorting
The previous examples all focused on techniques for sorting a list in place. Another option we can consider is to maintain our List in sorted order. The List class contains a method BinarySearch() that enables us to achieve this goal. To make dealing with the behavior a bit clearer, we will create a custom MySortedList<T> class, which under the hood, will still use List<T>, but will maintain it in a sorted state. For brevity, we will not explore the entire class here.
Class Definition for Custom Sorting
First, let’s take a look at our class definition:
public sealed class MySortedList<T> : IList<T> where T : IComparable<T>
Because our goal is to maintain the sort order of our collection, we are restricting our type parameter T to those that implement IComparable<T>. Since we are creating a special type of list, we will also implement the IList<T> interface, so that we can use our sorted list in most places where we would use a standard List<T>.
Having said that, the fact that this list will always maintain a sorted order does add a couple of restrictions regarding the IList<T> interface. Namely, there are a couple of methods in the interface that we will not implement, but rather throw a NotSupportedException.
The first one is the Insert(int index, T item) method. Since our requirement is that our list is always sorted, we cannot support inserting at a specific index. Secondly, and related to the insert issue, is allowing set() through the indexer []. Retrieving a value at a given index is fully supported, but we cannot support setting the value, as that could lead to the list becoming unsorted.
Constructor Definitions
Just like List, we allow setting the initial capacity of the list through the constructor. Because we are maintaining the list in sorted order, we also allow for passing in a custom ICompare<T> which, if provided, will be used to define the sort order:
public MySortedList(int capacity = 0, IComparer<T>? comparer = null)
{
_list = new List<T>(capacity);
_comparer = comparer;
}
Not shown are the class member variables for _list and _comparer, but from the constructor, we see that _list is our internal List<T> and _comparer is the IComparer<T> that we will use if it is provided.
For ease of use and to mirror List<T> we will also provide a constructor which takes an IEnumerable<T>:
public MySortedList(IEnumerable<T> initialValues, IComparer<T>? comparer = null) : this(comparer: comparer)
=> AddRange(initialValues);
With this constructor, we chain into our earlier constructor and then we pass the initialValues into our AddRange() function.
Adding Elements to Our Custom List Implementation
Our Add() method is where our new friend BinarySearch() really shines. As the name suggests, it searches through a sorted collection using a binary search strategy. Upon finding a matching element, it returns its index. When the element is not found, it returns a negative number that is the bitwise complement of the index of the next larger element. This means that by taking the complement, we get the insertion index for this item. Let’s take a look at our Add() method:
public void Add(T item)
{
var index = _list.BinarySearch(item, _comparer);
if (index < 0) index = ~index;
_list.Insert(index, item);
}
On line #3 we see that the first thing we do, when adding, is to search for a matching item using BinarySearch(). The next step is to check whether the returned index is negative or not. As we mentioned earlier, in the case of a negative value (item not found), by taking the complement, we get our insertion index. The last step, line #6, is to perform the actual insertion. Since we are allowing duplicate items in our list, we simply insert the item at the computed index. We insert the new item in the list if we find a matching item. If no item was found, we insert the new item at the location computed by the complement of the BinarySearch() result.
It will probably be clearer to understand this by walking through a simple example.
Using BinarySearch to Maintain Sort Order When Inserting
Let’s say we have the array of integers that we wish to insert into our custom MySortedList:
var data = new int[] {5, 1, 5, 3};
Now let’s loop through them, adding each one to our sorted list:
var sortedList = new MySortedList<int>(); foreach(var num in data) sortedList.Add(num);
The first time through the loop (5), the internal list is empty, so when we get to line #3 in the Add() method, BinarySearch() will return -1. Taking the complement, we get 0, and so we insert our element at index 0. And after the first iteration of the loop our list now looks like this: {5}
On our second iteration (1), BinarySearch() once again returns -1 as the item does not exist, and belongs at the beginning of the list (complement of -1 being 0). Now, our list looks like this: {1, 5}.
On our third iteration (5), BinarySearch() returns 1 as expected, since 5 already exists in our list. We insert the new item at the found index, and now have the following list: {1, 5, 5}.
Our fourth iteration (3), is where it gets a bit more interesting. This time BinarySearch() returns -2. Because the value is negative, we know the item was not found in the list. Taking the complement yields an index of 1, and so we insert the item at this location. After inserting, our final list looks like this: {1, 3, 5, 5}
Adding a Range of Elements
When it comes to adding a range of elements, we have two options. One option is to loop over the elements, calling our Add() method to insert each one in the proper location. The other option is to add them all to the end of the list and then sort it. We have chosen to implement the latter option due to the overall performance improvement. For completeness, let’s take a look at the method:
public void AddRange(IEnumerable<T> items)
{
_list.AddRange(items);
_list.Sort(_comparer);
}
If the collection being added is small, there is not much difference in performance between the two options. As items length increases, we will begin to see a difference in performance (to not stray too far from the topic of the article, we are leaving measuring the performance as an exercise to the reader). The main reason is that Add(), on average, inserts elements into the middle of the list. Each time this occurs, the element at the chosen index and all following elements must be shifted down by one. As the number of elements being inserted grows, the cost involved in moving the elements becomes larger. By contrast, adding all the elements at once reduces the number of large copies being done.
Conclusion
In this article, we have explored several different techniques for sorting a list in place. We have looked at List.Sort() and its associated overloads, and we have implemented our own always-sorted collection. One thing we have not mentioned is using LINQ to enumerate our collection in an ordered fashion. Never fear, we have an article covering exactly that topic, so be sure to check it out!
