List.Sort() producing unexpected results

After spending a very long time being frustrated that my list of item wouldn't sort reliably and usually not correctly, I finally found out why. The built-in List.Sort() is "not stable", which means items evaluated to be equal are not guaranteed to be in the same order.

This produces a faster sorting, but in my case, produced undesirable results. I was making a dependency sort (using a custom Comparison delegate) where one XElement item would need to be processed before another if a dependency link existed. As you can imagine, the default Sort did not work when more than two items were in the list.

The solution came from an article I found that alerted me of the Sort being unstable. It also had a link to a stable Sort, which I've adapted to a .Net 3.5 Extension method.

        /// <summary>

        /// Sorts the <seealso cref="System.Collections.Generic.List<>"/> using a

        /// stable sorting method to gurantee that items that evaluate to equal

        /// are preserved in the correct order.

        /// </summary>

        /// <typeparam name="T">The list containment type.</typeparam>

        /// <param name="list">The list.</param>

        /// <param name="comparison">The comparison.</param>

        /// <remarks>This method uses an InsertSort.</remarks>

        /// <remarks>Source: http://www.csharp411.com/c-stable-sort/</remarks>

        /// <exception cref="System.ArgumentNullException">Occurs when <paramref name="list"/> or <paramref name="comparison"/> are null</exception>

        public static void StableSort<T>(this List<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 = i-1)

                {

                    list[i + 1] = list[i];

                }

                list[i + 1] = key;

            }

        }