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

c#, complexity-theory, linq, sql-order-by

Solution

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.)

Problem

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).

Original source