Simple Sorting in .Net With Comparison and IComparer

Sorting is an important piece for just about any programmer's job. The ability to effectively search and sort often has a significant impact on the execution time of a batch job and on the user's measure of "responsiveness" in a traditional GUI or web based application. There are a number of people that go through and write their own implementations of common sorting algorithms (insertion sort, bubble sort, merge sort, etc.), but I prefer to use built in library functions whenever possible.

Many of the collection types in System.Collections implement a Sort() method that can be used to sort data in a (mostly) arbitrary way. I say mostly in this case because an inconsistent comparison may lead to an ArgumentException.

There are a few basic rules to remember. Given a Comparison or IComparer that compares objects x (the first argument) and y (the second argument), the following may happen:

• If the comparison returns -1 (or any value less than 0), object x will be placed before y.
• If the comparison returns 0, object x and y will retain their positions.
• If the comparison returns 1 (or any value greater than 0), object y will be placed before object x.

To begin, let's look at a very simple example of an ascending (low -> high) sort and a descending (high -> low) sort (note that the examples given here are given as Visual Studio Unit Tests):

        [TestMethod]

        public void AscendingSort()

        {

            List<int> unsorted = new List<int>(new int[] { 2, 1, 3 });

            unsorted.Sort((x, y) =>

            {

                int retval;

                if (x < y) { retval = -1; }

                else if (x == y) { retval = 0; }

                else { retval = 1; }

                return retval;

            });

            Assert.AreEqual(1, unsorted[0]);

            Assert.AreEqual(2, unsorted[1]);

            Assert.AreEqual(3, unsorted[2]);

        }

-->

        [TestMethod]

        public void DescendingSort()

        {

            List<int> unsorted = new List<int>(new int[] { 2, 1, 3 });

            unsorted.Sort((x, y) =>

            {

                int retval;

                if (x < y) { retval = 1; }

                else if (x == y) { retval = 0; }

                else { retval = -1; }

                return retval;

            });

            Assert.AreEqual(3, unsorted[0]);

            Assert.AreEqual(2, unsorted[1]);

            Assert.AreEqual(1, unsorted[2]);

        }

-->

Since the integer types implement the IComparable interface, these examples can be written more compactly as:

        [TestMethod]

        public void AscendingSort()

        {

            List<int> unsorted = new List<int>(new int [] { 2, 1, 3});

           

            unsorted.Sort((x, y) =>

            {

                return x.CompareTo(y);

            });

            Assert.AreEqual(1, unsorted[0]);

            Assert.AreEqual(2, unsorted[1]);

            Assert.AreEqual(3, unsorted[2]);

        }

        [TestMethod]

        public void DescendingSort()

        {

            List<int> unsorted = new List<int>(new int[] { 2, 1, 3 });

            unsorted.Sort((x, y) =>

            {

-->

                //could also be written as y.CompareTo(x)
                return -1 * x.CompareTo(y);

            });

            Assert.AreEqual(3, unsorted[0]);

            Assert.AreEqual(2, unsorted[1]);

            Assert.AreEqual(1, unsorted[2]);

        }

-->
It should be noted that if a collection contains objects that do not implement IComparable, the Sort() method will throw an InvalidOperationException unless a custom Comparison delegate or implementation of IComparer is used. People often run into this with List<T> and ArrayList<T>, among other specialized types.

Up until now, I've demonstrated using a System.Comparison delegate with the Sort() method. Here is an example of a class that implements IComparer and its use in a corresponding Sort() operation:

    public class AscendingComparison : IComparer<int>

    {

        public int Compare(int x, int y)

        {

            return x < y ? -1 : x == y ? 0 : 1;

        }

    }

        [TestMethod]

        public void AscendingSort()

        {

            List<int> unsorted = new List<int>(new int [] { 2, 1, 3});

           

            unsorted.Sort(new AscendingComparison());

            Assert.AreEqual(1, unsorted[0]);

            Assert.AreEqual(2, unsorted[1]);

            Assert.AreEqual(3, unsorted[2]);

        } --> -->

As a general pattern, the delegate form makes the most sense in simple code that is not expected to be reused (potentially with the transaction script pattern) because it is potentially difficult to modify if it becomes spread across multiple locations. More complex code (think object composition and more complex design patterns) or code that requires the ability to define a sort at runtime should implement IComparer in a different class that can be reused and centrally modified as necessary.

In the next set of examples, I'll look at more complex sorting scenarios.