Ah, right. Yes, I can see how that could happen :)

I did two tests. The first, below, ordered a list of ints. The ints
themselves were generated randomly, and in no partcular order.

       private void button1_Click(object sender, EventArgs e)
       {

           int i = 0, count = 1000000;

           IList<int> ints = this.GenerateInts(count),
               linqed = new List<int>(),
               sorted;

           int[] ordinals;

           double orderby,
               firstelement,
               nextelement,
               total,
               sorterQuick,
               sorterHeap,
               sorterMerge,
               sorterInsert;

           orderby = firstelement = nextelement = total = sorterQuick
= sorterHeap = sorterMerge = 0;

           HighPerformanceTimer timer1 = new HighPerformanceTimer(),
               timer2 = timer1.Clone() as HighPerformanceTimer;

           timer1.Start();
           timer2.Start();

           var a = ints.OrderBy( p => p, Comparer<int>.Default );

           timer1.Stop();
           
           orderby = timer1.ElapsedSeconds();

           timer1.Start();

           foreach (int val in a)
           {
               if (i == 0)
               {
                   timer1.Stop();
                   firstelement = timer1.ElapsedSeconds();
                   timer1.Start();
               }
               else
               {
                   if (i == 1)
                   {
                       timer1.Stop();
                       nextelement = timer1.ElapsedSeconds();
                   }
               }
               linqed.Add(val);
               i++;
           }

           timer2.Stop();
           total = timer2.ElapsedSeconds();

           System.Diagnostics.Debug.Print("Passed Linq sort
orderby={0}, firstelement={1}, nextelement={2}, total={3}", orderby,
firstelement, nextelement, total );

           ordinals = Sorter.GetOrdinals(count);
           timer1.Start();
           sorted = Sorter.SortPointers<int>( ordinals, ints,
SortMethod.HugeQuick);
           timer1.Stop();

           sorterQuick = timer1.ElapsedSeconds();
           System.Diagnostics.Debug.Print("Passed quick sort {0}",
sorterQuick);
           
           ordinals = Sorter.GetOrdinals(count);
           timer1.Start();
           sorted = Sorter.SortPointers<int>( ordinals, ints,
SortMethod.Heap);
           timer1.Stop();

           sorterHeap = timer1.ElapsedSeconds();
           System.Diagnostics.Debug.Print("Passed heap sort {0}",
sorterHeap);

           ordinals = Sorter.GetOrdinals(count);
           timer1.Start();
           sorted = Sorter.SortPointers<int>( ordinals, ints,
SortMethod.Merge);
           timer1.Stop();

           sorterMerge = timer1.ElapsedSeconds();
           System.Diagnostics.Debug.Print("Passed merge sort {0}",
sorterMerge);

       }

This produced the following output:

Passed Linq sort orderby=1.36772072165396E-06,
firstelement=0.507163260675607, nextelement=1.70756239620126E-06,
total=0.577546772172414
Passed quick sort 0.459738433186191
Passed heap sort 1.21546727261184
Passed merge sort 0.763105243653448

I took this to mean that an order by operation is about 25% slower via
LINQ than doing a comparable quicksort.

The second test was filtering. The code for this is here:

       private void button2_Click(object sender, EventArgs e)
       {
           int i = 0, count = 1000000;

           IList<int> ints = this.GenerateInts(count),
               linqed = new List<int>();

           double whereclause,
               sortthencustomfilter,
               customfilter;

           whereclause = sortthencustomfilter = customfilter = 0;

           HighPerformanceTimer timer1 = new HighPerformanceTimer();

           timer1.Start();

           var a = ints.Where(p => p > count/2);

           foreach (int val in a)
           {
               linqed.Add(val);
               i++;
           }

           timer1.Stop();
           whereclause = timer1.ElapsedSeconds();

           System.Diagnostics.Debug.Print("Passed Linq where filter:
whereclause={0}", whereclause);

           timer1.Start();
           IList<int> newList = new List<int>();

           for (i = 0; i < count; i++)
           {
               if (ints[i] < count / 2)
               {
                   newList.Add(ints[i]);
               }
           }
           timer1.Stop();

           customfilter = timer1.ElapsedSeconds();
           System.Diagnostics.Debug.Print("Passed filter only in {0},
difference={1}", customfilter, 1-customfilter/whereclause);
       }

and the output here:

Passed Linq where filter: whereclause=0.030069347417103
Passed filter only in 0.018763416394604, difference=0.375995224162012

LINQ is 37% slower at picking out elements from a list was what I got
out of this.

At this point I quit looking at it. For my purposes, losing double
digit percentages off performance just isn't acceptable. I suppose
that might be acceptable to others, though.