LINQ To Objects GroupBy method

Question

How does LINQ To Objects GroupBy method work? Does it look throught the whole collection for each key? Is there any way to say to GroupBy method that collection is sorted?

Answer 1

GroupBy, if done sensibly, would work in a single forwards only pass. A basic implementation (not theirs) would be something comparable to:

var data = new Dictionary<TKey, List<TValue>>(comparer);
foreach(var item in source) {
    var key = keySelector(item);
    List<TValue> list;
    if(!data.TryGetValue(key, out list))
    {
        data.Add(key, list = new List<TValue>());
    }
    list.Add(itemSelector(item));
}

That basically groups by key, creating a list for each unique key, containing the values.

You could do things like compare to the last-seen key (to help with sorted data), but... you'd need to profile to know if it is worthwhile.