Is the sorting algorithm used by .NET's `Array.Sort()` method a stable algorithm?
C#.NetC# Problem Overview
Is the sorting algorithm used by .NET's Array.Sort()
method a stable algorithm?
C# Solutions
Solution 1 - C#
From MSDN: >This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.
The sort uses introspective sort. (Quicksort in version 4.0 and earlier of the .NET framework).
If you need a stable sort, you can use Enumerable.OrderBy.
Solution 2 - C#
Adding to Rasmus Faber's answer…
Sorting in LINQ, via Enumerable.OrderBy and Enumerable.ThenBy, is a stable sort implementation, which can be used as an alternative to Array.Sort. From Enumerable.OrderBy documentation over at MSDN:
> This method performs a stable sort; > that is, if the keys of two elements > are equal, the order of the elements > is preserved. In contrast, an unstable > sort does not preserve the order of > elements that have the same key.
Also, any unstable sort implementation, like that of Array.Sort
, can be stabilized by using the position of the elements in the source sequence or array as an additional key to serve as a tie-breaker. Below is one such implementation, as a generic extension method on any single-dimensional array and which turns Array.Sort
into a stable sort:
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);
}
}
}
Below is a sample 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);
}
}
Below is the output from the sample program above (running on a machine with Windows Vista SP1 and .NET Framework 3.5 SP1 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 }
Solution 3 - C#
As other answers have stated, Array.Sort isn't stable. However, the LINQ OrderBy methods (and OrderByDescending etc) are stable, which can be very useful.
Solution 4 - C#
No, it isn't:
> This method uses the QuickSort algorithm. This implementation performs an unstable sort
Solution 5 - C#
UPDATE: This code not stabilizing Array.Sort (ensure that the elements 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;
};
}
}
Use:
Comparison<Person> comparison = (x, y) => x.BirthYear.CompareTo(y.BirthYear);
Array.Sort(unstable, comparison.WithGetHashCode());