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

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

Which Sorting Algorithm used in .NET Array’s Sort method ? (Array.Sort( ))

Which sorting algorithm is used in .NET’s Array Sort method ? (Array.Sort( ))

Fast stable sorting algorithm implementation in javascript

I’m looking to sort an array of about 200-300 objects, sorting on a specific key and a given order (asc/desc). The order of results must be consistent and stable. What would be the best algorithm to u

Fast stable sorting algorithm implementation in javascript

I’m looking to sort an array of about 200-300 objects, sorting on a specific key and a given order (asc/desc). The order of results must be consistent and stable. What would be the best algorithm to u

DataView sort method – which sorting algorithm is used?

I am using VS2012, .NET Framework 4.5. I need to know which sorting algorithm is used in DataView.Sort? My code: var table = new DataTable(); table.Columns.Add(Word); table.DefaultView.Sort = Word

What is the reason why sorting algorithm is stable or unstable? [closed]

I want to understand the main reason why sorting algorithm becomes stable or unstable. I understand that every unstable algorithm can become stable if we add one more position key to the element. (But

Is there a black box method to detect if a sorting algorithm is stable?

In JavaScript (somewhat applicable elsewhere), where you don’t know what target implementation your code is running on, is there a way to feature detect if the underlying sorting algorithm (of Array.s

Stable Marriage Algorithm Proof

I am unable to prove a lemma which is required in the proof of correctness of Gayle Shapley Algorithm for Stable marriage problem. Lemma During the algorithm, each Boy A is rejected only by girls that

Which sorting algorithm is used by .net in IComparer

Do any one know which sorting algorithm is used by .net when we implement IComparer in our class?

which sorting algorithm is used for std::list’s sort member function? [duplicate]

Possible Duplicate: Which sorting algorithm is used by STL’s list::sort()? Which sorting algorithm can be used for sorting std::list ?

Is there a stable sorting algorithm for .Net Doubles faster than O(n log n)?

I need a stable sorting algorithm for .Net Doubles that is faster than O(n log n). I am thinking of Radix sort. However if I understand correctly, it’s performance is O(n k) and since I’m sorting Doub

Answers

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.

No, it isn’t:

This method uses the QuickSort algorithm. This implementation performs an unstable sort

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.

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 }

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());