Is the sorting algorithm used by the .NET `Array.Sort ()` method a robust algorithm?

Question

Is the sorting algorithm used by the .NET Array.Sort() method a stable algorithm?

Answer 1

From MSDN :

This implementation performs unstable sorting; that is, if two elements are equal, their order may not be preserved. In contrast, robust sorting preserves the order of equal elements.

The variety uses an introspective look. (Quicksort in version 4.0 and earlier of the .NET framework).

If you need stable sorting, you can use Enumerable.OrderBy .

Answer 2

Adding Rasmus Faber to the answer ...

Sorting in LINQ through Enumerable.OrderBy and Enumerable.ThenBy is a stable sort implementation that can be used as an alternative to Array.Sort . From the Enumerable.OrderBy documentation on MSDN :

This method performs stable sorting; that is, if the keys of the two elements are equal, the order of the elements is preserved. In contrast, erratic sorting does not preserve the order of items that have the same key.

In addition, any unstable sorting implementation, like the Array.Sort function, can be stabilized by using the position of elements in the original sequence or array as an additional key for use as a tie-breaker. Below is one such implementation, as a universal extension method for any one-dimensional array and which turns Array.Sort into a stable form:

 using System; using System.Collections.Generic; public static class ArrayExtensions { public static void StableSort<T>(this T[] values, Comparison<T> comparison) { var keys = new KeyValuePair<int, T>[values.Length]; for (var i = 0; i < values.Length; i++) keys[i] = new KeyValuePair<int, T>(i, values[i]); Array.Sort(keys, values, new StabilizingComparer<T>(comparison)); } private sealed class StabilizingComparer<T> : IComparer<KeyValuePair<int, T>> { private readonly Comparison<T> _comparison; public StabilizingComparer(Comparison<T> comparison) { _comparison = comparison; } public int Compare(KeyValuePair<int, T> x, KeyValuePair<int, T> y) { var result = _comparison(x.Value, y.Value); return result != 0 ? result : x.Key.CompareTo(y.Key); } } } 

The following is an example of a program using StableSort from above:

 static class Program { static void Main() { var unsorted = new[] { new Person { BirthYear = 1948, Name = "Cat Stevens" }, new Person { BirthYear = 1955, Name = "Kevin Costner" }, new Person { BirthYear = 1952, Name = "Vladimir Putin" }, new Person { BirthYear = 1955, Name = "Bill Gates" }, new Person { BirthYear = 1948, Name = "Kathy Bates" }, new Person { BirthYear = 1956, Name = "David Copperfield" }, new Person { BirthYear = 1948, Name = "Jean Reno" }, }; Array.ForEach(unsorted, Console.WriteLine); Console.WriteLine(); var unstable = (Person[]) unsorted.Clone(); Array.Sort(unstable, (x, y) => x.BirthYear.CompareTo(y.BirthYear)); Array.ForEach(unstable, Console.WriteLine); Console.WriteLine(); var stable = (Person[]) unsorted.Clone(); stable.StableSort((x, y) => x.BirthYear.CompareTo(y.BirthYear)); Array.ForEach(stable, Console.WriteLine); } } sealed class Person { public int BirthYear { get; set; } public string Name { get; set; } public override string ToString() { return string.Format( "{{ BirthYear = {0}, Name = {1} }}", BirthYear, Name); } } 

The following is the output from the above program (runs on a computer with Windows Vista Service Pack 1 and .NET Framework 3.5 installed):

 { BirthYear = 1948, Name = Cat Stevens } { BirthYear = 1955, Name = Kevin Costner } { BirthYear = 1952, Name = Vladimir Putin } { BirthYear = 1955, Name = Bill Gates } { BirthYear = 1948, Name = Kathy Bates } { BirthYear = 1956, Name = David Copperfield } { BirthYear = 1948, Name = Jean Reno } { BirthYear = 1948, Name = Jean Reno } { BirthYear = 1948, Name = Kathy Bates } { BirthYear = 1948, Name = Cat Stevens } { BirthYear = 1952, Name = Vladimir Putin } { BirthYear = 1955, Name = Bill Gates } { BirthYear = 1955, Name = Kevin Costner } { BirthYear = 1956, Name = David Copperfield } { BirthYear = 1948, Name = Cat Stevens } { BirthYear = 1948, Name = Kathy Bates } { BirthYear = 1948, Name = Jean Reno } { BirthYear = 1952, Name = Vladimir Putin } { BirthYear = 1955, Name = Kevin Costner } { BirthYear = 1955, Name = Bill Gates } { BirthYear = 1956, Name = David Copperfield } 

Answer 3

As the other answers pointed out, Array.Sort is unstable. However, the LINQ methods of OrderBy (and OrderByDescending, etc.) are stable, which can be very useful.

Answer 4

No, not :

This method uses the QuickSort algorithm. This implementation performs unstable sorting.

Answer 5

UPDATE: This code does not stabilize Array.Sort (make sure the items are always sorted in the same order):

 public static class ComparisonExtensions { public static Comparison<T> WithGetHashCode<T>(this Comparison<T> current) { return (x, y) => { var result = current(x, y); if (result == 0) return x.GetHashCode() - y.GetHashCode(); return result; }; } } 

Using:

 Comparison<Person> comparison = (x, y) => x.BirthYear.CompareTo(y.BirthYear); Array.Sort(unstable, comparison.WithGetHashCode());