Performance question on IOrderedEnumerable

See more:

C#

VB

LINQ

C#4.0

collections

.NET4

I just stumbled upon an oddity in IOrderedEnumerable.Contains[^] and was wondering if more people here had the problem or if it is just me...

Consider the following code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> list = new List<int>();
            for (int i = 0; i < 1000000; i++)
            {
                list.Add(i);
            }
            
            IOrderedEnumerable<int> orderedList = list.OrderBy(i => i);
            
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            for (int i = 0; i < 100; i++)
            { list.Contains(923456); }
            sw.Stop();
            Console.WriteLine("Calling contains on the List 100 times cost " + sw.Elapsed.ToString());
            
            sw.Reset();
            sw.Start();
            for (int i = 0; i < 100; i++)
            { orderedList.Contains(923456); }
            sw.Stop();
            Console.WriteLine("Calling contains on the IOrderedEnumerable 100 times cost " + sw.Elapsed.ToString());
            
            Console.ReadKey();
        }
    }
}

Nothing wrong there... I am building a list with a million (unique) integers. Even though it is already sorted I am calling the OrderBy Extension Method[^] and I get an IOrderedEnumerable<int>[^].
Now I call the Contains Method[^] of the original list 100 times with a value of which I know will be somewhere at the back (assuming a List<T>[^] will scan every element until it finds the one I am looking for this will take almost the maximum amount of time to find it).
After that I do the same on the IOrderedEnumerable<T>, but I call the IEnumerable<T>.Contains Extension Method[^]. I am expecting that this will pretty much do the same as List<T>.Contains which is scanning every item in the collection until it finds the one I'm looking for.
Now that shouldn't be to difficult. But I was pretty surprised by the result!
List.Contains took about 0,7 to 0,8 seconds for 100 iterations... IOrderedEnumerable.Contains took a whooping 38 seconds!!!
I then added this little gem:

sw.Reset();
sw.Start();
for (int i = 0; i < 100; i++)
{ orderedList.ToList().Contains(923456); }
sw.Stop();
Console.WriteLine("Calling contains on the IOrderedEnumerable.ToList 100 times cost " + sw.Elapsed.ToString());

And it took 40 seconds! Somehow copying the list 100 times and calling Contains only takes 2 seconds longer then only calling Contains...
I also tried changing 923456 to 1 to make sure it was found rather quickly, but it actually made no difference (it did for the List<T> though).
I am shocked, stunned, surprised and clueless...

Am I missing something here? I had expected both collections to take more or less the same time to compute... In fact, since an IOrderedEnumerable<T> is ordered it could find values MUCH faster if it searched using a Comparer[^] rather than an EqualityComparer[^].

Any idea's? I'm out of them...