OrderBy().First() Wasn't Sorting Anything

I left a comment on a pull request last week that I now regret. The code found the cheapest offer for a product like this:

var cheapest = offers.OrderBy(o => o.Price).First();

And I did the thing. "This sorts the whole list just to grab one item. Use MinBy, it's a single pass." I even added a little explainer about O(n log n) versus O(n), feeling helpful. Then I went to prove it with a benchmark so the author couldn't argue, and the benchmark made me look silly instead.

What I expected

My mental model was simple and, I thought, obviously correct. OrderBy sorts everything. Sorting a hundred thousand items means roughly 1.7 million comparisons and a buffer big enough to hold them all. MinBy walks the list once, keeps the smallest it's seen, and allocates nothing. So swapping one for the other should be a clean win on both time and garbage. That's the kind of change you make without thinking.

Here's the setup I ran it against. A hundred thousand offers, each a small record, cheapest price sitting somewhere in the middle so neither approach gets to cheat by position:

record Offer(int Id, string Seller, decimal Price, int StockDays);

static Offer CheapestViaOrderBy(List<Offer> offers)
    => offers.OrderBy(o => o.Price).First();

static Offer CheapestViaMinBy(List<Offer> offers)
    => offers.MinBy(o => o.Price)!;

I measured best-of-N per call, warmed the JIT first, and tracked allocations with GC.GetAllocatedBytesForCurrentThread(). This is a shared cloud container, not a quiet lab machine, so I care about the ratios between these numbers, not the absolute milliseconds.

What actually happened

OrderBy().First():    0.675 ms/call      128 bytes/call
MinBy():              0.654 ms/call       40 bytes/call

A tie. Same speed, within noise. MinBy allocated less, but we're talking 40 bytes against 128, not the megabytes I was picturing. There was no sort to avoid, because OrderBy().First() wasn't sorting anything.

That stopped me. I'd been so sure. So I went and read what LINQ actually does, and it turns out the ordering operators are lazier than I gave them credit for. OrderBy on its own doesn't sort. It builds an IOrderedEnumerable that describes a sort and defers the work until someone enumerates it. And First() doesn't enumerate the sorted result. It has a special path that asks the ordered sequence for just its first element, and that path computes the minimum in a single comparison pass. No buffer, no full sort. The same is true for Last(), and ElementAt has its own partial-selection trick too.

So the code I told someone to "fix" was already doing the O(n) single pass I was about to recommend. MinBy expresses the intent better, and it shaves a few bytes, but it is not rescuing the performance of that line. It can't. There was never a fire.

Where the sort is real

The sort only happens when you make it happen, which is the moment you ask for the whole ordered sequence instead of one end of it. Materialize it and the bill comes due:

static Offer CheapestViaFullSort(List<Offer> offers)
    => offers.OrderBy(o => o.Price).ToList()[0];

OrderBy().ToList()[0]:   26.466 ms/call   3,602,961 bytes/call

There's the sort I kept imagining. Against OrderBy().First() that's about 39 times slower and roughly twenty-eight thousand times the allocation per call. That gap is the actual lesson. The danger was never OrderBy().First(). It's the .ToList(), the .ToArray(), the foreach over the ordered result, or taking the top three with .OrderBy(...).Skip(2).First(), which genuinely does have to order things. If you only want one end of a sequence, say so with First, Last, Min, or Max, and LINQ keeps it cheap. The expensive version is the one that keeps the sorted copy around.

So is MinBy pointless?

No, and this is where I landed after being wrong. I still reach for MinBy in that pull request, just not for the reason I gave. It says what the code means in one word. Nobody reading MinBy(o => o.Price) has to pause and remember that OrderBy().First() happens to be optimized. And it's a little quieter on allocation. Those are fine reasons. "It avoids a sort" is not one, because there wasn't a sort.

One honest caveat before you swap everything on sight: the two don't behave the same on an empty sequence, and I got bitten by exactly this once.

OrderBy().First() -> throws InvalidOperationException
MinBy()           -> returns null   (for a reference type)

First() throws when there's nothing there. MinBy over a sequence of reference types hands you back null instead, which is easy to miss if you're not expecting it and leads to a NullReferenceException three lines later that points at the wrong place. Over value types like List<int>, MinBy throws just like First does. So the swap can quietly turn a loud exception into a silent null. Worth a glance at the call site before you trust it.

My takeaway, stated as the opinion it is: micro-advice about LINQ performance is worth almost nothing without a measurement next to it, and I'm including my own advice in that. I was confidently, specifically wrong about a line I've "optimized" a dozen times. The benchmark took ten minutes and saved me from being wrong in writing.

Here's the whole thing if you want to run it yourself. I'd meant to drop a GitHub link here, but the repo push was blocked in my build environment this run, so the full sample is inline instead:

using System.Diagnostics;

record Offer(int Id, string Seller, decimal Price, int StockDays);

static class Bench
{
    const int Count = 100_000;
    const int Iterations = 200;

    static List<Offer> BuildOffers(int n)
    {
        var rng = new Random(1234);
        var list = new List<Offer>(n);
        for (int i = 0; i < n; i++)
            list.Add(new Offer(i, "seller-" + (i % 500),
                rng.Next(100, 100_000) / 100m, rng.Next(0, 30)));
        return list;
    }

    static Offer CheapestViaOrderBy(List<Offer> o) => o.OrderBy(x => x.Price).First();
    static Offer CheapestViaMinBy(List<Offer> o)   => o.MinBy(x => x.Price)!;
    static Offer CheapestViaFullSort(List<Offer> o) => o.OrderBy(x => x.Price).ToList()[0];

    static (double ms, long bytes) Measure(Func<List<Offer>, Offer> find, List<Offer> offers)
    {
        find(offers);
        for (int i = 0; i < 20; i++) find(offers);

        double best = double.MaxValue;
        long bytesBest = long.MaxValue;
        var sw = new Stopwatch();
        for (int rep = 0; rep < 5; rep++)
        {
            long before = GC.GetAllocatedBytesForCurrentThread();
            sw.Restart();
            for (int i = 0; i < Iterations; i++) find(offers);
            sw.Stop();
            long after = GC.GetAllocatedBytesForCurrentThread();
            best = Math.Min(best, sw.Elapsed.TotalMilliseconds / Iterations);
            bytesBest = Math.Min(bytesBest, (after - before) / Iterations);
        }
        return (best, bytesBest);
    }

    static void Main()
    {
        var offers = BuildOffers(Count);
        var (a, ba) = Measure(CheapestViaOrderBy, offers);
        var (b, bb) = Measure(CheapestViaMinBy, offers);
        var (c, bc) = Measure(CheapestViaFullSort, offers);

        Console.WriteLine($"OrderBy().First():     {a,8:F3} ms   {ba,12:N0} bytes/call");
        Console.WriteLine($"MinBy():               {b,8:F3} ms   {bb,12:N0} bytes/call");
        Console.WriteLine($"OrderBy().ToList()[0]: {c,8:F3} ms   {bc,12:N0} bytes/call");
    }
}

Did you also carry around the "OrderBy().First() sorts everything" belief, or was that just me? Curious whether anyone's hit the empty-sequence null in production.

Still benchmarking lines of code that nobody filed a bug against.