IList Sorting: A Better Way

Programming forums across the web are replete with questions about how to sort an IList. Many .NET developers have discovered that, unlike List, IList does not define a Sort() method. Although there are many excellent answers to the question of how to sort an IList on the forums, none of them are as convenient, elegant, and complete as they could be.

Today, I will show you how to create a C# extension method to add Sort() functionality to IList that behaves just like the List.Sort() method. As a bonus, we can use the same technique to overload the LINQ Enumerable.OrderBy() extension method to allow it to accept a Comparison delegate, rather than a key selector or IComparer.

Get the Code

The Goal: How We Want IList Sorting to Work

If you're a C# developer, chances are you've used the List class and its built-in Sort() method, which provides very convenient syntax to sort a list in-place using a lambda expression.

Let's look at a simple example. Say we have a list of names that we want to sort by string length:

List list = new List 
{ 
	"Carlton", "Alison", "Bob", "Eric", "David"
};

// Sort by Length using a lambda expression 
// (which is equivalent to a Comparison delegate)
list.Sort((s1, s2) => s1.Length.CompareTo(s2.Length));

// Write out the results
foreach (string name in list)
{
	Console.WriteLine(name);
}

// OUTPUT:
// Bob
// Eric
// David
// Alison
// Carlton

Our goal is to provide this exact same syntax, but for an IList.

So How Can We Add this Functionality to IList?

Easy! We'll use a few extension methods. Without further ado, the code:

public static class SortExtensions
{
	//  Sorts an IList in place.
	public static void Sort(this IList list, Comparison comparison)
	{
		ArrayList.Adapter((IList)list).Sort(new ComparisonComparer(comparison));
	}

	// Convenience method on IEnumerable to allow passing of a 
	// Comparison delegate to the OrderBy method.
	public static IEnumerable OrderBy(this IEnumerable list, Comparison comparison)
	{
		return list.OrderBy(t => t, new ComparisonComparer(comparison));
	}
}

// Wraps a generic Comparison delegate in an IComparer to make it easy 
// to use a lambda expression for methods that take an IComparer or IComparer
public class ComparisonComparer : IComparer, IComparer
{
	private readonly Comparison _comparison;

	public ComparisonComparer(Comparison comparison)
	{
		_comparison = comparison;
	}

	public int Compare(T x, T y)
	{
		return _comparison(x, y);
	}

	public int Compare(object o1, object o2)
	{
		return _comparison((T)o1, (T)o2);
	}
}

Breaking it Down.

First things first: How can we sort an IList, anyway? Fortunately, we don't have to write our own sorting algorithm, since the .NET framework provides a way to get the job done. The ArrayList.Adapter method may be used to wrap the IList in an ArrayList, and then we can use the ArrayList's Sort() method on the wrapped list. This will have the effect of sorting the list in-place, without needing to make an in-memory copy.

ArrayList.Adapter(ilist).Sort( ... );

Defining the IList.Sort() Extension Method

Since our goal is to mimic the List.Sort() method, we must be able to accept a lamdba expression—in the form of a Comparison delegate—into the Sort() method, like so:

public static void Sort(this IList list, Comparison comparison)
{
	// Compiler error! Comparison is not an IComparer
	ArrayList.Adapter((IList)list).Sort(comparison); 
}

We're almost there, but sadly, the extension method defined above will not compile. ArrayList.Sort() takes an IComparer, not a Comparison. Our goal, however, is to accept a Comparison, so how can we make that happen?

Wrapping the Comparison Delegate

The answer is that we can wrap the Comparison in a class implementing IComparer and IComparer. We'll call the class ComparisonComparer, since it is an IComparer that works by using a Comparison delegate.

public class ComparisonComparer : IComparer, IComparer
{
	private readonly Comparison _comparison;

	public ComparisonComparer(Comparison comparison)
	{
		_comparison = comparison;
	}

	public int Compare(T x, T y)
	{
		return _comparison(x, y);
	}

	public int Compare(object o1, object o2)
	{
		return _comparison((T)o1, (T)o2);
	}
}

Now that we have our ComparisonComparer, we can complete the Sort extension:

public static void Sort(this IList list, Comparison comparison)
{
	// Now it works!
	ArrayList.Adapter((IList)list).Sort(new ComparisonComparer(comparison)); 
}

Bonus: Enumerable.OrderBy()

List.Sort() and ArrayList.Sort() are quick and easy to use, but they are both backed by the same implementation of the QuickSort algorithm in Array.Sort, which has one potential drawback: it's an unstable sorting algorithm. From MSDN:

The LINQ OrderBy() extension method provides an alternative way to sort a list, and utilizes a stable sorting algorithm. However, OrderBy() requires different syntax and will only accept a key selector delegate and/or an IComparer, rather than a Comparison. Fortunately, the same technique that we used for IList may be applied to OrderBy():

public static IEnumerable OrderBy(this IEnumerable list, Comparison comparison)
{
	return list.OrderBy(t => t, new ComparisonComparer(comparison));
}

This technique unifies the various sorting methods, so that whether you're using List.Sort, IList.Sort, or IEnumerable.OrderBy, you can use the exact same syntax.

Using the New Extensions

There you have it! These extensions unify the syntax for several disparate sorting methods built-in to the .NET Framework. Simply include the SortExtensions classes in your project, and you can use a lambda expression (or other delegate) to easily sort ILists and IEnumerables:

IList iList = new []
{ 
	"Carlton", "Alison", "Bob", "Eric", "David"
};

// Use the custom extensions:

// Sort in-place
iList.Sort((s1, s2) => s1.Length.CompareTo(s2.Length));

// Or use OrderBy()
IEnumerable ordered = iList.OrderBy((s1, s2) => s1.Length.CompareTo(s2.Length));