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.
| Method | Stable |
|---|---|
Array.Sort, Span.Sort | no |
List<T>.Sort | no |
Enumerable.OrderBy, OrderByDescending, ThenBy | yes |
Enumerable.Order, OrderDescending | yes |
SortedSet, SortedList, SortedDictionary | no 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.
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.
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.
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.
(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.
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.
#: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#:
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
- Merge sort
- Quick sort
- Heap sort
- Counting sort
- Radix sort
- Bucket sort
- Array.Sort and Span.Sort
- Binary search
- Introsort
- Quickselect
- External sort
- Timsort
Author
List all C# tutorials.