ZetCode

C# stable sorting

last modified November 15, 2026

In this article we explain stable sorting in C#. We show that Array.Sort and List.Sort are not stable, and we get a stable order with LINQ's OrderBy and with index decoration. We also sort by several keys with ThenBy.

Sorting is arranging the elements of a collection in a specific order, for instance from the smallest to the largest. A sorting algorithm is the sequence of steps that produces this order.

Stable sort

A sort is stable if elements that compare as equal keep their original relative order. When we sort integers, stability does not matter, because two equal integers cannot be told apart. When we sort records by one of their fields, it does: two employees from the same department are equal for the sort, but they are different employees.

MethodStable
Array.Sort, Span.Sortno
List<T>.Sortno
Enumerable.OrderBy, OrderByDescending, ThenByyes
Enumerable.Order, OrderDescendingyes
SortedSet, SortedList, SortedDictionaryno duplicate keys

The in-place sorts use introsort, which is a quicksort variant and moves equal elements past each other. LINQ sorts are stable by specification. Of the classic algorithms, insertion sort, merge sort and Timsort are stable; quick sort, heap sort and selection sort are not.

List.Sort vs OrderBy

The first example sorts twenty employees by their department with List.Sort and with OrderBy.

Program.cs
string[] depts = ["IT", "HR", "Sales"];
string[] names = ["Alice", "Bob", "Carol", "Dave", "Erin", "Frank", "Grace", "Heidi",
    "Ivan", "Judy", "Ken", "Liam", "Mia", "Nina", "Oscar", "Paul", "Quinn", "Rose",
    "Sam", "Tina"];

List<Employee> emps = [.. names.Select((n, i) => new Employee(n, depts[i * 7 % 3]))];

Console.WriteLine("input:     " + Names(emps, "IT"));

List<Employee> a = [.. emps];
a.Sort((x, y) => string.CompareOrdinal(x.Dept, y.Dept));
Console.WriteLine("List.Sort: " + Names(a, "IT"));

List<Employee> b = [.. emps.OrderBy(e => e.Dept, StringComparer.Ordinal)];
Console.WriteLine("OrderBy:   " + Names(b, "IT"));

static string Names(List<Employee> emps, string dept) =>
    string.Join(" ", emps.Where(e => e.Dept == dept).Select(e => e.Name));

record Employee(string Name, string Dept);

The employees are assigned to the IT, HR and Sales departments. We print the IT employees in the order they appear in each list.

a.Sort((x, y) => string.CompareOrdinal(x.Dept, y.Dept));

List.Sort scrambles the order of the IT employees. Paul is now first, Alice last.

List<Employee> b = [.. emps.OrderBy(e => e.Dept, StringComparer.Ordinal)];

OrderBy keeps them in the input order, which was alphabetical.

Arrays and lists with up to 16 elements are sorted by insertion sort, which happens to be stable. With such small test data, List.Sort seems stable, and the bug appears only on larger inputs.

$ dotnet run
input:     Alice Dave Grace Judy Mia Paul Sam
List.Sort: Paul Mia Judy Grace Dave Sam Alice
OrderBy:   Alice Dave Grace Judy Mia Paul Sam

Index decoration

Any unstable sort becomes stable if we break the ties by the original position. We pair each element with its index, sort the pairs, and copy the elements back.

Program.cs
string[] words = ["sky", "forest", "cup", "war", "ocean", "book", "cloud", "tea",
    "river", "pen", "lamp", "fox", "storm", "map", "rain", "ice", "wind", "sun",
    "tree", "bee"];

string[] a = [.. words];
Array.Sort(a, (x, y) => x.Length.CompareTo(y.Length));
Console.WriteLine(string.Join(" ", a));

string[] b = [.. words];
StableSort(b, (x, y) => x.Length.CompareTo(y.Length));
Console.WriteLine(string.Join(" ", b));

static void StableSort<T>(T[] arr, Comparison<T> cmp)
{
    var keyed = new (T Item, int Index)[arr.Length];

    for (int i = 0; i < arr.Length; i++)
    {
        keyed[i] = (arr[i], i);
    }

    Array.Sort(keyed, (x, y) =>
    {
        int res = cmp(x.Item, y.Item);
        return res != 0 ? res : x.Index.CompareTo(y.Index);
    });

    for (int i = 0; i < arr.Length; i++)
    {
        arr[i] = keyed[i].Item;
    }
}

We sort words by their length with Array.Sort and with the stable version.

var keyed = new (T Item, int Index)[arr.Length];

The array of tuples holds each element together with its original index.

int res = cmp(x.Item, y.Item);
return res != 0 ? res : x.Index.CompareTo(y.Index);

If the comparison says the elements are equal, the one with the lower index goes first. No two pairs are equal, so the instability of Array.Sort has nothing to act on.

In the first line, the three-letter words are in a mixed order. In the second line, they keep the input order: sky, cup, war, tea and so on.

$ dotnet run
sky sun ice map fox tea pen war cup bee book tree lamp rain wind river ocean storm cloud forest
sky cup war tea pen fox map ice sun bee book lamp rain wind tree ocean cloud river storm forest

Sorting by several keys

To sort by several keys, we chain ThenBy and ThenByDescending after OrderBy.

Program.cs
Car[] cars =
[
    new("Skoda", "Octavia", 2019),
    new("Audi", "A4", 2021),
    new("Skoda", "Fabia", 2021),
    new("BMW", "X3", 2019),
    new("Audi", "A6", 2019),
    new("Skoda", "Superb", 2023),
    new("BMW", "320i", 2021),
];

var res = cars.OrderBy(c => c.Make).ThenByDescending(c => c.Year).ThenBy(c => c.Model);

foreach (var c in res)
{
    Console.WriteLine(c);
}

Console.WriteLine();

var twoPass = cars.OrderBy(c => c.Model).OrderByDescending(c => c.Year).OrderBy(c => c.Make);
Console.WriteLine($"same as ThenBy: {res.SequenceEqual(twoPass)}");

record Car(string Make, string Model, int Year);

We sort cars by make, then by year from the newest, then by model.

var res = cars.OrderBy(c => c.Make).ThenByDescending(c => c.Year).ThenBy(c => c.Model);

The secondary keys are used only when the previous keys are equal. All keys are evaluated once per element.

var twoPass = cars.OrderBy(c => c.Model).OrderByDescending(c => c.Year).OrderBy(c => c.Make);

Stability allows a different approach: sort by the least important key first and by the most important key last. Each stable pass keeps the order of the previous pass among equal elements. The result is the same, but it is less efficient than ThenBy, because it performs three full sorts. Repeated OrderBy calls are usually a bug: the author meant ThenBy.

$ dotnet run
Car { Make = Audi, Model = A4, Year = 2021 }
Car { Make = Audi, Model = A6, Year = 2019 }
Car { Make = BMW, Model = 320i, Year = 2021 }
Car { Make = BMW, Model = X3, Year = 2019 }
Car { Make = Skoda, Model = Superb, Year = 2023 }
Car { Make = Skoda, Model = Fabia, Year = 2021 }
Car { Make = Skoda, Model = Octavia, Year = 2019 }

same as ThenBy: True

Descending order and stability

How we get a descending order affects the order of equal elements.

Program.cs
(string Name, int Score)[] players =
[
    ("Anna", 80), ("Ben", 95), ("Cyril", 80), ("Dora", 95), ("Emil", 70), ("Fiona", 80),
];

var desc = players.OrderByDescending(p => p.Score);
Console.WriteLine("OrderByDescending:  " + string.Join(" ", desc.Select(p => p.Name)));

var reversed = players.OrderBy(p => p.Score).Reverse();
Console.WriteLine("OrderBy + Reverse:  " + string.Join(" ", reversed.Select(p => p.Name)));

var negated = players.OrderBy(p => -p.Score);
Console.WriteLine("OrderBy(-Score):    " + string.Join(" ", negated.Select(p => p.Name)));

Six players are sorted by their score from the highest.

var desc = players.OrderByDescending(p => p.Score);

OrderByDescending is stable: Ben comes before Dora, and Anna, Cyril and Fiona are in the input order.

var reversed = players.OrderBy(p => p.Score).Reverse();

Reversing an ascending sort also reverses the order of equal elements. Dora is now before Ben and Fiona before Anna.

var negated = players.OrderBy(p => -p.Score);

Negating a numeric key gives the same result as OrderByDescending. It fails for int.MinValue, whose negation overflows back to itself.

$ dotnet run
OrderByDescending:  Ben Dora Anna Cyril Fiona Emil
OrderBy + Reverse:  Dora Ben Fiona Cyril Anna Emil
OrderBy(-Score):    Ben Dora Anna Cyril Fiona Emil

Stable sort of a list in place

LINQ returns a new sequence. If other code holds a reference to the list, we can copy the sorted elements back into it.

Program.cs
using System.Runtime.InteropServices;

List<Job> jobs =
[
    new("write tests", 2), new("fix bug", 1), new("deploy", 3), new("review", 2),
    new("update docs", 3), new("refactor", 2), new("triage", 1), new("plan", 3),
    new("release notes", 3), new("cleanup", 2), new("benchmark", 2), new("hotfix", 1),
    new("design", 3), new("estimate", 2), new("demo", 3), new("retro", 3),
    new("upgrade", 2), new("monitor", 1),
];

Job[] sorted = [.. jobs.OrderBy(t => t.Priority)];
sorted.CopyTo(CollectionsMarshal.AsSpan(jobs));

foreach (var row in jobs.Chunk(6))
{
    Console.WriteLine(string.Join(", ", row.Select(t => $"{t.Priority} {t.Name}")));
}

record Job(string Name, int Priority);

We sort jobs by priority and keep the input order of jobs with the same priority.

Job[] sorted = [.. jobs.OrderBy(t => t.Priority)];
sorted.CopyTo(CollectionsMarshal.AsSpan(jobs));

The CollectionsMarshal.AsSpan method returns a span over the list's internal array. Copying into it overwrites the elements without allocating a new list. A simple jobs = [.. jobs.OrderBy(...)] would work too if nothing else references the list.

$ dotnet run
1 fix bug, 1 triage, 1 hotfix, 1 monitor, 2 write tests, 2 review
2 refactor, 2 cleanup, 2 benchmark, 2 estimate, 2 upgrade, 3 deploy
3 update docs, 3 plan, 3 release notes, 3 design, 3 demo, 3 retro

Performance

Is a stable sort slower? The last example sorts one million records by an integer key with values from 0 to 999, so there are many duplicates.

benchmark.cs
#:property PublishAot=false

using System.Diagnostics;

var rnd = new Random(17);
Item[] data = [.. Enumerable.Range(0, 1_000_000).Select(i => new Item(rnd.Next(1000), i))];

Measure("Array.Sort", a => Array.Sort(a, (x, y) => x.Key.CompareTo(y.Key)));
Measure("Array.Sort + index", a => StableSort(a, (x, y) => x.Key.CompareTo(y.Key)));
Measure("OrderBy", a => a.OrderBy(x => x.Key).ToArray());

void Measure(string name, Action<Item[]> sort)
{
    long best = long.MaxValue;

    for (int i = 0; i < 5; i++)
    {
        Item[] copy = [.. data];
        var sw = Stopwatch.StartNew();
        sort(copy);
        best = Math.Min(best, sw.ElapsedMilliseconds);
    }

    Console.WriteLine($"{name,-20} {best,4} ms");
}

static void StableSort<T>(T[] arr, Comparison<T> cmp)
{
    var keyed = new (T Item, int Index)[arr.Length];

    for (int i = 0; i < arr.Length; i++) keyed[i] = (arr[i], i);

    Array.Sort(keyed, (x, y) =>
    {
        int res = cmp(x.Item, y.Item);
        return res != 0 ? res : x.Index.CompareTo(y.Index);
    });

    for (int i = 0; i < arr.Length; i++) arr[i] = keyed[i].Item;
}

record Item(int Key, int Id);

We compare Array.Sort with a comparison, the index-decorated version, and OrderBy.

Measure("OrderBy", a => a.OrderBy(x => x.Key).ToArray());

OrderBy is the fastest here. It extracts all keys into an int array first and compares the integers directly, while the comparison delegate reads the Key property of two objects on every call. Index decoration adds another comparison and copying, and it is the slowest.

The stable LINQ sort is a good default for records. The extra memory it needs, an array of keys and an array of indexes, is rarely a problem.

$ dotnet run -c Release benchmark.cs
Array.Sort            173 ms
Array.Sort + index    242 ms
OrderBy               138 ms

Source

Enumerable.OrderBy method
List<T>.Sort method

In this article we have explained stable sorting in C#. See also Array.Sort and Span.Sort and sort List.

Other sorting articles in C#:

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all C# tutorials.