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.

Excellent!

Good, but there are much better stable sorts available, for example MergeSort and Binary tree sort, both of which have the same average time complexity as QuickSort (n log n).

See http://en.wikipedia.org/wiki/Stable_sort#Classification

Check out PowerCollections (http://www.wintellect.com/PowerCollections.aspx) for a stable sort implementation and many other useful functions…

(Source code is available)

[…] http://www.csharp411.com/c-stable-sort/ […]

Just what I was looking for. I too ran into the .NET quicksort stability problem. Insertion sort, although it is of higher time complexity O(N^2) than quicksort’s O(nlogn), ends up being better in practice for smaller collections as there is less overhead (space complexity for one, as this is an in-place algorithm) than, say, merge sort or heap sort. And of course it’s stable. Also it is said to be “adaptive” so if the data is “nearly sorted” it can outperform other DAC (divide and conquer) algorithms like merge sort. In fact you’ll often see “hybrid” sort algorithms using insertion sort when the problem size is small.

For large collections, no contest: merge sort.

BTW, I really like how the author has properly laid out the sort using generic types as it makes other convenient methods possible (such as delegate comparison functions). For those that do not want to explicitly implement the CompareTo method in their class (let’s say you have various keys you want to sort on determined at runtime, such as the columns in a gridview), you can use the author’s sort method like this:

// or name, etc, determined at runtime.

string SortKey = “age”;

InsertionSort(list, delegate(Person a, Person b) { if (SortKey == “name”) return a.Name.CompareTo(b.Name); else if (SortKey == “age”) return a.Name.CompareTo(b.Name); });

You can see how the anonymous delegate has scope over your SortKey variable which can be the user’s custom sort expression. Very useful stuff here especially when combined with the power of the .NET GridView control.

If yo uwant to reverse the sort direction, pass in a flag that tells you what the sort direction is (ascending or descending) and simply flip the person objects around:

bool AscendingSort = false;

// or name, etc, determined at runtime.

string SortKey = “age”;

InsertionSort(list, delegate(Person a, Person b) {

if (SortKey == “name”) {

if (AscendingSort) return a.Name.CompareTo(b.Name);

else return b.Name.CompareTo(a.Name);

} else if (SortKey == “age”) {

if (AscendingSort) return a.Age.CompareTo(b.Age);

else return b.Age.ComapreTo(a.Age);

}

return 0;

});

Brillaint!!!!! Thanks a lot!!!!!

Very Big Hug! Thank you…

Most of the example that I’ve seen sort a relatively simple structure made up of two objects (e.g., Person {Name, Birthday}). However, I am now faced with a more complex structure (i.e., HSLColor {Hus, Saturation, Lightness}). I also need to take into account a users desire to sort by HSL, HLS, SHL, SLH, LHS, or LSH. Assuming the desired sort order is a string named sort_order, then I am using

private int HSL_comparer ( HSLColor HSL_1,

HSLColor HSL_2 )

{

int HSL_H_comparison =

HSL_1.Hue.CompareTo (

HSL_2.Hue );

int HSL_L_comparison =

HSL_1.Luminosity.CompareTo (

HSL_2.Luminosity );

int HSL_S_comparison =

HSL_1.Saturation.CompareTo (

HSL_2.Saturation );

for ( var i = 0; ( i < sort_order.Length ); i++ )

{

switch ( sort_order.Substring ( i, 1 ) )

{

case "H":

if ( HSL_H_comparison != 0 )

{

return ( HSL_H_comparison );

}

break;

case "S":

if ( HSL_S_comparison != 0 )

{

return ( HSL_S_comparison );

}

break;

case "L":

if ( HSL_L_comparison != 0 )

{

return ( HSL_L_comparison );

}

break;

default:

break;

}

}

return ( 0 );

}

Of course, what I get is unstable. Any thoughts?

TIA