Sorted Fine at 16, Broke at 17

I had a ticket queue that sorted by priority and, within a priority, served tickets first-come-first-served. Simple comparer, one line, tickets.Sort((a, b) => a.Priority.CompareTo(b.Priority)). The unit test fed it a handful of tickets, checked the priority order, went green. Shipped it. A week later someone asked why a low-volume queue was fair and a busy one kept jumping newer tickets ahead of older ones at the same priority.

The comparer was right. The sort wasn't stable, and I'd never noticed because my test was too small to trip it.

Small lists lie

List<T>.Sort and Array.Sort use an introspective sort: quicksort that bails to heapsort, with insertion sort for small runs. None of that promises to keep equal elements in their original order. But here's the part that fooled me. Below a size threshold, the runtime just uses insertion sort, which happens to be stable. So tiny inputs come back looking perfectly ordered, and your test passes with a lie.

I didn't want to argue from memory, so I probed it. Same priority on every ticket, arrivals numbered 0, 1, 2, … in order, then sort by priority and check whether the arrival numbers are still ascending.

record Ticket(int Arrival, int Priority);

static List<Ticket> SameBucket(int n)
{
    var list = new List<Ticket>(n);
    for (int i = 0; i < n; i++)
        list.Add(new Ticket(Arrival: i, Priority: 5)); // all equal keys
    return list;
}

static bool ArrivalsStillAscending(IEnumerable<Ticket> sorted)
{
    int last = int.MinValue;
    foreach (var t in sorted)
    {
        if (t.Arrival < last) return false;
        last = t.Arrival;
    }
    return true;
}

foreach (int n in new[] { 8, 16, 17, 32, 100, 1000 })
{
    var a = SameBucket(n);
    a.Sort((x, y) => x.Priority.CompareTo(y.Priority));
    bool listSortStable = ArrivalsStillAscending(a);

    var b = SameBucket(n);
    var ordered = b.OrderBy(t => t.Priority).ToList();
    bool orderByStable = ArrivalsStillAscending(ordered);

    Console.WriteLine($"{n,4} | {(listSortStable ? "yes" : "NO"),-17} | {(orderByStable ? "yes" : "NO")}");
}

The output, on .NET 10:

size | List.Sort stable? | OrderBy stable?
-----+-------------------+----------------
   8 | yes               | yes
  16 | yes               | yes
  17 | NO                | yes
  32 | NO                | yes
 100 | NO                | yes
1000 | NO                | yes

Sixteen is fine. Seventeen is not. That's not a number worth memorizing, since it's an implementation detail that can move between runtimes, but it explains exactly how I got burned. My test had five tickets. Production queues had dozens. The code was identical. One of them was quietly reordering and the other wasn't, and nothing in the type system or the test told me which.

What it does to a real queue

Here's the damage on a mixed queue. Twenty tickets, priorities 1 through 3 interleaved as they arrive, then sorted by priority. I pulled out just the priority-1 tickets and looked at their arrival numbers, which is the order a human would be served in.

var bySortP1 = new List<Ticket>(queue);
bySortP1.Sort((x, y) => x.Priority.CompareTo(y.Priority));
var listArrivalsP1 = bySortP1.Where(t => t.Priority == 1).Select(t => t.Arrival);

var byOrderP1 = queue.OrderBy(t => t.Priority)
                     .Where(t => t.Priority == 1)
                     .Select(t => t.Arrival);

priority-1 arrival order, List.Sort : 1, 17, 3, 5, 14, 8, 11
priority-1 arrival order, OrderBy   : 1, 3, 5, 8, 11, 14, 17

Ticket 17 jumped ahead of tickets 3, 5, 8, 11 and 14. It showed up last and got served second. If that queue is support tickets, someone who waited twenty minutes watched a latecomer cut the line. The OrderBy version serves them in arrival order, every time, which is what I meant all along.

Why OrderBy gets it right

LINQ's OrderBy is documented as a stable sort, and it keeps that promise at every size I tried. It does it by remembering each element's original index and using that as the final tiebreaker under the hood. That costs something. It buffers the whole sequence and allocates to do the ordering, so it's not free. List<T>.Sort sorts in place and is generally cheaper on big, hot collections where you genuinely don't care which of two equal elements comes first.

So I'm not telling you to delete every List.Sort. If order among equal keys doesn't matter, say you're sorting numbers, or you're about to render a set where ties are interchangeable, in-place Sort is the right tool and the allocation-free one.

What I actually do now

When tie order matters, my honest preference isn't "reach for OrderBy and trust the stability guarantee." It's to make the tiebreaker explicit in the comparison, because stability is invisible at the call site. Six months later nobody reading tickets.Sort(byPriority) can see that correctness secretly depends on insertion order being preserved.

tickets.Sort((x, y) =>
{
    int byPriority = x.Priority.CompareTo(y.Priority);
    return byPriority != 0 ? byPriority : x.Arrival.CompareTo(y.Arrival);
});

Now the comparer fully determines the result. No equal elements are ever left for the sort to shuffle, so stability stops mattering, and the next person can read the intent right there in the code. If I'm in LINQ already, OrderBy(t => t.Priority).ThenBy(t => t.Arrival) says the same thing just as plainly.

The lesson I keep relearning: a sort that looks ordered in a small test isn't the same as a sort that's defined. If two elements can tie, decide what happens to them on purpose.

Have you been bitten by an unstable sort in production, or do you always spell out the tiebreaker? I'd like to know whether I'm the only one who learned this the hard way.

— still sorting things nobody asked me to sort