How to find the first item according to a specific ordering using LINQ in O(n)?

Question

Suppose I have a list of items (e.g., Posts) and I want to find the first item according to some non-trivial ordering (e.g., PublishDate and then CommentsCount as a tie-breaker). The natural way to do this with LINQ is like this:

posts.OrderBy(post => post.PublishDate).ThenBy(post => post.CommentsCount).First()

However, the micro-optimizer in me is worried that calling OrderBy actually costs me O(n*lgn) for sorting the entire list, when all I really need is an O(n) find-minimum operation.

So, is LINQ smart enough to return something from OrderBy() that knows how to optimize subsequent First() calls? If not, what's a better way to do this out-of-the-box? (I can always write my own FindMinimumItem implementation but that seems like overkill).

Answer 1

The sorting is smart in the way that it will only do the ThenBy on the first group from the OrderBy, but the OrderBy still has to sort all items before it can return the first group.

You can use the Aggregate method to get the first post according to a custom comparison:

Post lowest =
  posts.Aggregate((Post)null,
    (x, y) =>
      x == null
      || y.PublishDate < x.PublishDate
      || (y.PublishDate == x.PublishDate && y.CommentsCount < x.CommentsCount)
      ? y : x
  );

(Assuming that you are using LINQ to Objects of course.)