The problem for LINQ is that it can't know the sorted set is ordered exactly the same way as the query expects. Since any ordered collection can be created with an IComparer
/ IComparable
/ Comparison<T>
, there is no knowing that > 500000
actually makes sense. Maybe you've got a custom method on the comparer that first sorts by Odd/Even, then by number. In which case the order would be completely messed up and O(n) is required in all cases.
So to be on the safe side, LINQ will need to iterate through all elements in the Collection, even when it is sorted in some way. The default .Where
implementation does not contain an optimization for ordered collections.
It might be possible to create an optimized version which keeps the existing ordering in mind while iterating, but it will be very difficult to do and to make it work in all cases.
You could create a Between
method that uses the GetViewBetween
method of SortedSet
to return a new pre-ordered collection. Or would add the standard .Where
as you'd normally would for any non-pre-sorted set.
Linq-to-SQL and Entity Framework make use if the IQueryable and will actually translate your Linq query to SQL and let the server handle the indexing, sorting, filtering etc.