CODEWITHSUNDEEP
c#linq
Dimitri
Dimitri

Reputation: 2878

How does OrderBy extension method orders collection

Suppose we have a class Foo which has an Int32 Field Bar and you want to sort the collection of the Foo objects by the Bar Value. One way is to implement IComparable's CompareTo() method, but it can also be done using Language Integrated Query (LINQ) like this

List<Foo> foos = new List<Foo>();
// assign some values here
var sortedFoos = foos.OrderBy(f => f.Bar);

now in sortedFoos we have foos collection which is sorted. But if you use System.Diagnostics.StopWatch object to measure the time it took OrderBy() to sort the collection is always 0 milliseconds. But whenever you print sortedFoos collection it's obviously sorted. How is that possible. It takes literary no time to sort collection but after method execution the collection is sorted ? Can somebody explain to me how that works ? And also one thing. Suppose after sorting foos collection I added another element to it. now whenever I print out the collection the the element I added should be in the end right ? WRONG ! The foos collection will be sorted like, the element I added was the part of foos collection even if I add that element to foos after sorting. I don't quit understand how any of that work so can anybody make it clear for me ?!

Upvotes: 2

Views: 2756

Answers (4)

Jodrell
Jodrell

Reputation: 35726

The OrderBy extension uses the deault IComparer for the type it is working on, unless an alternative is passed via the appropriate overload.

The sorting work is defered until the IOrderedEnumerable<T> returned by your statement is first accessed. If you place the Stopwatch around that first access, you'll see how long sorting takes.

This makes a lot of sense, since your statement could be formed from multiple calls that return IOrderedEnumerables. As the ordering calls are chained, they fluently extend the result, allowing the finally returned IOrderedEnumerable to perform the sorting in the most expedient way possible. This is probably achieved by chaining all the IComparer calls and sorting once. A greedy implementation would have to wastefully sort multiple times.

For instance, consider

class MadeUp
{
    public int A;
    public DateTime B;
    public string C;
    public Guid D;
}

var verySorted = madeUps.OrderBy(m => m.A)
                    .ThenBy(m => m.B)
                    .ThenByDescending(m => m.C)
                    .ThenBy(m => m.D);

If verySorted was evaluated greedily, then every property in the sequence would be evaluated and the sequence would be reordered 4 times. Because the linq implementation of IOrderedEnumerable deferes sorting until enumeration, it is able to optimise the process.

The IComparers for A, B, C and D can be combined into a composite delegate, something like this simplified representation,

int result
result = comparerA(A, B);
if (result == 0)
{
    result = comparerB(A, B);
    if (result == 0)
    {
        result = comparerC(A, B);
        if (result == 0)
        {
            result = comparerD(A, B);
        }
    }
}

return result;

the composite delegate is then used to sort the sequence once.

Upvotes: 1

S.N
S.N

Reputation: 5140

LINQ believe in deferred execution. This means the expression will only be evaluated when you started iterating or accessing the result.

Upvotes: 3

Peter
Peter

Reputation: 27944

You have to add the ToList() to get a new collection. If you do't the OrderBy will be called when you start iterating on sortedFoos.

List<Foo> foos = new List<Foo>();
// assign some values here
var sortedFoos = foos.OrderBy(f => f.Bar).ToList();

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1502466

Almost all LINQ methods use lazy evaluation - they don't immediately do anything, but they set up the query to do the right thing when you ask for the data.

OrderBy follows this model too - although it's less lazy than methods like Where and Select. When you ask for the first result from the result of OrderBy, it will read all the data from the source, sort all of it, and then return the first element. Compare this to Select for example, where asking for the first element from the projection only asks for the first element from the source.

If you're interested in how LINQ to Objects works behind the scenes, you might want to read my Edulinq blog series - a complete reimplementation of LINQ to Objects, with a blog post describing each method's behaviour and implementation.

(In my own implementation of OrderBy, I actually only sort lazily - I use a quick sort and sort "just enough" to return the next element. This can make things like largeCollection.OrderBy(...).First() a lot quicker.)

Upvotes: 5

Related Questions