A Short History of Sorting in C#

Recently, while reading Jon Skeet’s excellent book“C# in Depth” I came across the long and varied history of sorting in the C# language. It provides a tantalising view of how the language has evolved over the years. Apart from being a great example on C# in particular it’s also a good example on how languages have improved over the years to become more expressive, while maintaining backward compatibility with earlier versions.

Take the simple act of sorting a list of objects, like for example products, shown here.

internal class Product
{
    public string Name { get; set; }
    public decimal Price { get; set; }
 
    public static List<Product> GetSampleProducts()
    {
        return new List<Product>
        {
            new Product { Name="Watership Down", Price = 6.25m },
            new Product { Name="The Color of Magic", Price = 7.00m },
            new Product { Name="Guards! Guards!", Price = 12.00m },
            new Product { Name="War and Peace", Price = 23.00m }    
        };
    }
}

Now you could go old school and implement your own [enter favourite algorithm here] sort routine, but for the more pedestrian programmer bent on actually getting things done, a more pragmatic approach in order. Imagine that your stuck on C# 1.0. You have an ArrayList of Product objects that you want to sort by Name. You could use the ArrayList.Sort method along with an IComparer object like so.

private class ProductNameComparer : IComparer
{
    public int Compare(object x, object y)
    {
        Product first = x as Product;
        Product second = y as Product;
 
        if (x == null || y == null)
            throw new InvalidCastException("Objects passed in are not Products.");
        return first.Name.CompareTo(second.Name);
    }
}
 
ArrayList products = new ArrayList(Product.GetSampleProducts());
products.Sort(new ProductNameComparer());

You could get the Product class itself to implement the IComparer interface, but then your stuck with sorting Product objects with just one field, i.e. in this case the name. Using an externally implemented class allows you to choose which Product field you want to target for the sort. You could very well create a ProductPriceComparer object that will be used by the Sort routine to compare the prices of a product.

There are a couple of things that could be improved with this method though. First, there is the verbosity. That’s a lot of code just to tell the language to sort something in alphabetical order. Then there are the casts within the IComparer.Compare method. This is probably something that you want to avoid as casting can result in runtime errors if the objects in the array list are not what you expected them to be. Note, as aside, I’ve used “as” to cast as opposed to the Product first = (Product)x style cast as its considered safer. Fortunately things improve in C# 2 with Generics.

class TypedProductNameComparer : IComparer<Product>
{
    public int Compare(Product x, Product y)
    {
        return x.Name.CompareTo(y.Name);
    }
}
     
List<Product> products = Product.GetSampleProducts();
products.Sort(new TypedProductNameComparer());

That code looks much cleaner now. You can see we’ve gotten rid of the ugly casts, thanks to the generic IComparer interface. Still its a lot of code to get something trivial done, besides what if you want to sort by the product price instead of the name? Well, C# 2 also introduces anonymous methods that can be used instead of the comparer when sorting the list. This results in far less code to get the same job done.

List<Product> products = Product.GetSampleProducts();
products.Sort(delegate (Product x, Product y) {
    return x.Name.CompareTo(y.Name);
});

Still, the syntax is a bit ugly. Enter C# 3.0 with lambda functions which allow for more simplified syntax to get the same job done.

List<Product> products = Product.GetSampleProducts();
products.Sort((x, y) => x.Name.CompareTo(y.Name));

Wow, that’s terse, specially considering where we started off. Finally to finish off, C# 3 also offers the ability to iterate things in order, without actually sorting the list

List<Product> products = Product.GetSampleProducts();
foreach (Product product in products.OrderBy(p => p.Name))
{
    // Do something useful
}