Sorting in .NET: stability and comparers

In real code you will almost never write your own sort. .NET’s built-in sorts are fast and well tested. What you do need to get right is which method to call, how to describe the order you want, and whether equal items may be reordered.

Stability matters

A stable sort keeps items with equal keys in their original order. That matters when the input already has a meaningful order, such as beams listed in erection sequence that you now want grouped by profile, or when you sort by one key and then by another.

// Stable, returns a new sequence
var sorted = beams.OrderBy(b => b.Profile)
     .ToList();

// In place, NOT guaranteed stable
list.Sort((x, y) =>
{
    return x.Profile.CompareTo(y.Profile);
});

Sorting by several keys

1var beams = new List<Beam>2{3    new("B1", "IPE300", 6.0), new("B2", "HEA200", 4.5),4    new("B3", "IPE300", 4.5), new("B4", "HEA200", 6.0)5};6 7// LINQ: readable, stable, returns a new list8var byProfileThenLongest = beams9    .OrderBy(b => b.Profile)10    .ThenByDescending(b => b.Length)11    .ToList();12 13foreach (var b in byProfileThenLongest)14    Console.WriteLine($"{b.Name} {b.Profile} {b.Length:0.0}");15 16// In place with a Comparison<T> lambda (no new list)17beams.Sort((x, y) =>18{19    int c = string.Compare(x.Profile, y.Profile, StringComparison.Ordinal);20    return c != 0 ? c : y.Length.CompareTo(x.Length);   // y before x = descending21});22 23record Beam(string Name, string Profile, double Length);

B4 HEA200 6.0
B2 HEA200 4.5
B1 IPE300 6.0
B3 IPE300 4.5

Three ways to define an order

• `IComparable<T>` on the type itself: its natural order. int, string, DateTime already have one. Then list.Sort() needs no arguments.
• `IComparer<T>`: a separate object describing an order. Useful when there are several orders, or you cannot change the type. Comparer<T>.Create(lambda) makes one from a lambda.
• `Comparison<T>`: a plain lambda (x, y) => int, accepted by List<T>.Sort and Array.Sort.

1var levels = new List<Level> { new("Roof", 12.0), new("Ground", 0.0), new("First", 4.0) };2levels.Sort();                                         // uses CompareTo3Console.WriteLine(string.Join(", ", levels.Select(l => l.Name)));4 5class Level : IComparable<Level>6{7    public string Name { get; }8    public double Elevation { get; }9    public Level(string name, double elevation) => (Name, Elevation) = (name, elevation);10 11    // negative: this comes first, 0: equal, positive: other comes first12    public int CompareTo(Level? other) => other is null ? 1 : Elevation.CompareTo(other.Elevation);13}

Ground, First, Roof

Classic sorting bugs

1. Subtracting to compare. (x, y) => x - y looks clever but overflows: for int.MinValue and 1 the result wraps around to a large positive number, so the order is wrong. Always use x.CompareTo(y).

2. Text order surprises. Strings are compared character by character, so "B10" comes before "B2" (because 1 < 2). The default comparer is also culture-sensitive. For IDs and file names, decide explicitly:

1var names = new List<string> { "apple", "Banana", "cherry" };2 3names.Sort(StringComparer.Ordinal);            // by character code: capitals first4Console.WriteLine(string.Join(" ", names));5 6names.Sort(StringComparer.OrdinalIgnoreCase);  // ignore case, culture-independent7Console.WriteLine(string.Join(" ", names));8 9var marks = new List<string> { "B10", "B2", "B1" };10marks.Sort(StringComparer.Ordinal);11Console.WriteLine(string.Join(" ", marks));    // text order, not number order

Banana apple cherry
apple Banana cherry
B1 B10 B2

3. Inconsistent comparers. A comparer must be consistent: if a < b and b < c then a < c, and comparing an item with itself gives 0. A comparer that uses random numbers or rounds values unevenly can make Sort throw InvalidOperationException (“IComparer.Compare() method returns inconsistent results”) or produce garbage.

4. Sorting what you only need partly. If you need only the 10 longest beams out of a million, sorting everything is O(n log n). A PriorityQueue of size 10 does it in O(n log 10), see the heaps lesson.

1var drawings = new List<string> { "A-10", "A-2", "B-1", "A-1" };2 3var sorted = drawings4    .OrderBy(d => d.Split('-')[0], StringComparer.Ordinal)5    .ThenBy(d => int.Parse(d.Split('-')[1]))6    .ToList();7 8Console.WriteLine(string.Join(", ", sorted));

A-1, A-2, A-10, B-1