A sort is stable if the original order of equal elements is preserved. An unstable sort does not guarantee that equal elements will appear in their original order after sorting.

The Sort methods used by the .NET collections are unstable. These sort methods, which include System.Array.Sort and System.Collections.Generic.List<T>.Sort, use the QuickSort algorithm, which is relatively fast but in this case, unstable. However, there may be instances where you require a stable sort, so a custom solution is required.

Simple Example

A stable sort can be best illustrated with an example. Consider the following simple Person class with Name and Age fields. The class also implements the IComparable interface that has the CompareTo method, which in this example sorts the Person objects by Age:

class Person : IComparable
{
    public Person( string name, int age )
    {
        this.Name = name;
        this.Age = age;
    }
    public string Name;
    public int Age;
    public int CompareTo( object obj )
    {
        int result = 1;
        if (obj != null && obj is Person)
        {
            Person person = (Person)obj;
            result = this.Age.CompareTo( person.Age );
        }
        return result;
    }
    public override string ToString()
    {
        return String.Format( "{0} - {1}", this.Name, this.Age );
    }
}

Now let’s create, sort and write a collection of Person objects:

Person p1 = new Person( "Abby", 38 );
Person p2 = new Person( "Bob", 23 );
Person p3 = new Person( "Charlie", 23 );
Person p4 = new Person( "Danielle", 18 );

List<Person> list = new List<Person>();
list.Add( p1 );
list.Add( p2 );
list.Add( p3 );
list.Add( p4 );
list.Sort();

Console.WriteLine( "Unstable List Sort:" );
foreach (Person p in list)
{
    Console.WriteLine( p );
}

In their original order, Bob (age 23) appears before Charlie (also age 23). But because both objects have the same age, and the List<T>.Sort method is unstable, the order of equal objects is reversed. Here is the output from the code above:

Unstable List Sort:
Danielle – 18
Charlie – 23
Bob – 23
Abby – 38

Stable Insertion Sort

There are many stable sorts available. The Insertion Sort is one of the more simple but efficient stable sorts:

public static void InsertionSort<T>( IList<T> list, Comparison<T> comparison )
{
    if (list == null)
        throw new ArgumentNullException( "list" );
    if (comparison == null)
        throw new ArgumentNullException( "comparison" );

    int count = list.Count;
    for (int j = 1; j < count; j++)
    {
        T key = list[j];

        int i = j - 1;
        for (; i >= 0 && comparison( list[i], key ) > 0; i--)
        {
            list[i + 1] = list[i];
        }
        list[i + 1] = key;
    }
}

Notice the InsertionSort<T> method requires a Comparison<T> delegate, so we need to add a static Compare method in the Person class with the Comparison<T> signature. For reliability, Compare simply calls the Person’s CompareTo method:

static public int Compare( Person x, Person y )
{
    int result = 1;
    if (x != null && x is Person &&
        y != null && y is Person)
    {
        Person personX = (Person)x;
        Person personY = (Person)y;
        result = personX.CompareTo( personY );
    }
    return result;
}

Now let’s clear the list, add the person objects again, and this time use our stable insertion sort:

list.Clear();
list.Add( p1 );
list.Add( p2 );
list.Add( p3 );
list.Add( p4 );
InsertionSort<Person>( list, Person.Compare );

Console.WriteLine( "Stable Insertion Sort:" );
foreach (Person p in list)
{
    Console.WriteLine( p );
}

As you can see from the output below of the code above, Bob appears before Charlie, and the original order of equal elements is preserved:

Stable Insertion Sort:
Danielle – 18
Bob – 23
Charlie – 23
Abby – 38

Sort Methods Compared

As this C Programming article explains, the Insertion Sort has an algorithmic efficiency of O(n^2) and in the best case (already sorted) has a constant time O(n). The QuickSort is more efficient with an average efficiency of O(n*log(n)). So in general you should use the .NET built-in Sort methods and use the Insertion Sort only if you explicitly require a stable sort.

Share and Enjoy:
  • Digg
  • Twitter
  • Facebook
  • Reddit
  • StumbleUpon
  • LinkedIn
  • Google Bookmarks
  • Slashdot