Article: Sorting a collection

The .NET Framework offers lots of classes that collect something, and these collections have a Sort() method to put the elements in a specific order. Examples of such classes are Array, ArrayList and List<Type>. Also some Windows Controls contain lists that can be sorted.

The sorting algorithms

A lot of different algorithms exist for sorting a collection; they have strange names such as Bubble Sort, QuickSort, and many more. I am not going to explore them; if you're interested there is ample material available, such as Knuth's third volume on the Art of Computer Programming. It suffices to say they all share the need for some code to "compare" two elements (i.e. determine their relative order); and they differ in functional characteristics, the two most important ones being:

1. performance: how long does it take to sort a collection holding N elements? This depends on the algorithm, and for some of them also depends on the initial state of the collection: being almost sorted may or may not speed up a full sort.
2. stability: as long as all elements are different, there would be a unique sorting order; however as soon as two or more elements have an indeterminate order (because they are identical or only differ in data not used as a sorting criterion), there original order may or may not be preserved. Algorithms are called "stable" when they do preserve the order of indeterminate elements.

Array.Sort() and other Sort methods based on it, such as List<T>.Sort(), are documented as follows: This Sort() method uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.

Default sorting

Basic data types offer a default sorting order by implementing the IComparable interface. Examples:

• If you sort an int array, or an ArrayList containing ints, the numbers will be sorted in ascending numeric order;
• If you sort a string array, or an ArrayList containing strings, the strings will be sorted in alphabetical order;
• If you add different types to an ArrayList (say all kinds of integers; or ints and strings), you'll get an InvalidOperationException.

More complex types (such as System.Windows.Drawing.Point or System.IO.FileInfo) and user-defined types don't offer a default sorting order; they need to implement some interface (such as IComparable) to make collections holding them sortable.

IComparable: the basics

The IComparable interface consists of a single method which compares the current instance with another object of the same type and returns an integer that indicates whether the current instance precedes (return <0), follows (return >0), or occurs in the same position (return zero) in the sort order as the other object.

int CompareTo(Object obj);

Function CompareTo(ByVal obj As Object) As Integer

For numeric comparison of signed integers, one can simply return their difference, so for a user-defined type where a short variable would be the sort criterion, that would be:

class MyShortClass : IComparable {
    private short value;
	
    public int CompareTo(Object obj) {
        MyShortClass that=(MyShortClass)obj;
        return this.value-that.value;
    }
}

Public Class MyShortClass
    Implements IComparable

    Private value As Short

    Public Function CompareTo(ByVal obj As Object) _
    As Integer Implements IComparable.CompareTo
        Dim that As MyShortClass = obj
        Return Me.value - that.value
    End Function
End Class

so 5.CompareTo(3) would return 2, 5.CompareTo(5) would return 0, 5.CompareTo(31) would return -26. Please note how a typical implementation starts by casting the Object obj parameter to a local variable of the appropriate type.

For numeric comparison of unsigned integers (and signed integers wider than int), one can not simply return their difference, as it could be negative or too large. The easiest approach is relying on a basic type's CompareTo() method:

class MyUlongClass : IComparable {
    private ulong value;
	
    public int CompareTo(Object obj) {
        MyUlongClass that=(MyUlongClass)obj;
        return value.CompareTo(that.value);
    }
}

Class MyUlongClass
    Implements IComparable

    Private value As ULong

    Public Function CompareTo(ByVal obj As Object) _
    As Integer Implements IComparable.CompareTo
        Dim that As MyUlongClass = obj
        Return value.CompareTo(that.value)
    End Function
End Class

Other comparison interfaces

There are three more comparison interfaces: IComparer, IComparable<T> and IComparer<T>. They are all very similar.

The IComparer interface consists of a single method which compares two objects of the same type and returns an integer. Its advantage lies in the fact that it does not rely on the current instance of the class it is in, so it is symmetric in both operands, and can be located in an entirely different class (see also next chapter).

int Compare(Object obj1, Object obj2);

Public Function Compare(ByVal obj1 As Object, _
    ByVal obj2 As Object) As Integer

The IComparable<T> and the IComparer<T> interfaces are the generic twins of the IComparable and IComparer interfaces; they too consist of a single method and their main advantage is they do not need the initial cast(s) making them both safer and faster, as is true with all the generic collections stuff:

int CompareTo(T obj);
int Compare(T obj1, T obj2);

Function CompareTo(ByVal that As T) As Integer
Function Compare(ByVal obj1 As T, _
    ByVal obj2 As T) As Integer

This is an example of an IComparer<T> interface for some type T that should be sorted according to some numeric value field; it illustrates the advantage of generics:

public int Compare(T obj1, T obj2) {
    return obj1.value.CompareTo(obj2.value);
}

Public Function Compare(ByVal obj1 As T, ByVal obj2 As T) _
    As Integer Implements IComparer(Of T).Compare
    Return obj1.value.CompareTo(obj2.value)
End Function

More advanced issues

Three problems remain to be solved:

1. what object should implement the compare interface?
   

   The examples so far have added the CompareTo() method to the type of the items collected. That is simple, and works well provided your sorting criterion is fixed; it would not easily allow changes such as a reverse sort, since such decision is not really a characteristic of the items themselves, it rather is a characteristic of the collection.

   An alternative is to implement the IComparer or IComparer<T> interface in the collection itself, i.e. derive a specialized collection from its base type, and tell it how it should sort itself.

   The third and final way is by implementing a separate comparer, i.e. a class that only provides the IComparer or IComparer<T> interface. You might have a look at the StringComparer class which is a good example of this approach.

2. how to implement composite sort criteria?
   

   Multiple sort criteria are easy to implement; what you need is check each criterion in turn, from the first to the last, and stop as soon as a decision has been made. Here is the recommended pattern:

   // comparing two objects of type MyType
   public int CompareTo(Object obj) {
       MyType that=(MyType)obj;
       int diff=this.Value1-that.Value1;	// comparing two signed integer values (major sort criterion)
       if (diff==0) diff=string.Compare(this.Name, that.Name); // comparing two strings
       if (diff==0) diff=this.Value2.CompareTo(that.Value2);   // comparing two ulongs (last sort criterion)
       return diff;
   }
   

   ' comparing two objects of type MyType
   Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
       Dim that As MyType = obj
       Dim diff As Integer
       diff = Me.Value1 - that.Value1    ' comparing two signed integer values (major sort criterion)
       If diff = 0 Then diff = String.Compare(Me.Name, that.Name) ' comparing two strings
       If diff = 0 Then diff = Me.Value2.CompareTo(that.Value2)   ' comparing two ulongs (last sort criterion)
       Return diff
   End Function
   

3. how to implement variable sort criteria?
   

   To modify a sort criterion at run-time you need a variable that holds such information; that variable must be part of your comparer class, hence the IComparer interface must be implemented either in a specialized collection or in a separate class. You then can set the controlling variable(s) before performing the sort. The example shows a simple up/down sorter for strings:

   // comparing two objects of type MyType based on a string and a selectable order
   private bool descending;
   
   public int Compare(Object obj1, Object obj2) {
       MyType this1=(MyType)obj1;
       MyType that2=(MyType)obj2;
       int diff=string.Compare(this1.Name, that2.Name);  // comparing two strings
       if (descending) diff= -diff;                      // invert the sort order
       return diff;
   }
   

   ' comparing two objects of type MyType based on a string and a selectable order
   Private descending As Boolean
   
   Public Function Compare(ByVal obj1 As Object, ByVal obj2 As Object) _
   As Integer Implements IComparer.Compare
       Dim this1 As MyType = obj1
       Dim that2 As MyType = obj2
       Dim diff As Integer
       diff = String.Compare(this1.Name, that2.Name)  ' comparing two strings
       If (descending) Then diff = -diff              ' invert the sort order
       Return diff
   End Function
   

Putting it all together (C#)

The final example puts all the above together; it shows a class MyType and a comparer class for collections holding instances of MyType.

public class MyType {
    // private fields
    private int value1;
    private string name1;
    private ulong value2;
	
    // and public getter properties
    public int Value1 { get {return value1;}}
    public string Name1 { get {return name1;}}
    public int Value2 { get {return value2;}}
    ...
}

public class MyTypeComparer : IComparer<MyType> {
    private bool descending;
	
    public MyTypeComparer(bool descending) {
        this.descending=descending;
    }
	
    public int Compare(MyType obj1, MyType obj2) {
        int diff=obj1.Value1-obj2.Value1;	// comparing two signed integer values (major sort criterion)
        if (diff==0) {
            diff=string.Compare(obj1.Name, obj2.Name); // comparing two strings
            if (descending) diff= -diff;
        }
        if (diff==0) diff=obj1.Value2.CompareTo(obj2.Value2);   // comparing two ulongs (last sort criterion)
        return diff;
    }
}

    // create a list
    List<MyType> list=new List<MyType>();
    list.Add(new MyType());
    ...
    // create a comparer
    MyTypeComparer comparer=new MyTypeComparer(true);
    // and use it to sort the list
    list.Sort(comparer);

Alternative C# syntax

Within the list.Sort(comparer) statement, one can replace the IComparer object by an anonymous delegate, like so:

    list.Sort(delegate(MyType obj1, MyType obj2) {
        int diff=obj1.Value1-obj2.Value1;
        ...
        return diff;
    });

For simple comparisons one can even use a lambda expression, like so:

    list.Sort((obj1, obj2) => obj1.Value1-obj2.Value1);

Sorting list Controls

For unknown reasons the list Controls in the System.Windows.Forms namespace use different semantics for sorting:

• DataGridView has a traditional Sort(IComparer) method;
• ListView and TreeView have a traditional Sort() method without parameters; they need their IComparer set beforehand through a separate property: ListView.ListViewItemSorter and TreeView.TreeViewNodeSorter;
• ListBox only knows how to sort strings alphabetically; if you need something else, the easiest way is by copying the list items to an array using ListBox.CopyTo(); then sorting that array, and clearing and restoring the items with ListBox.Items.Clear() and ListBox.AddRange().

Conclusion

You can sort .NET collections easily, all it takes is providing an appropriate comparison method.

History

• Version 1.0 (09-Aug-2009): Original version
• Version 1.1 (06-Sep-2009): Added VB.NET examples
• Version 1.2 (01-Feb-2010): Added chapter on alternative C# syntax
• Version 1.3 (30-Mar-2011): Vocabulary fixed (thanks Pete)