c# - Why is this Linq expression so much slower than the other? -

time of execution: foo(1) >>> foo(2) >> foo(3)

roughly: 1427349 >>> 14757 >> 1362

foo(3) optimized algorithm among three, i'm not surprised it's fastest. what's surprising me foo(2) faster foo(1). impression foo(2) sorts, while foo(1) operating foo(3). may know cause slowdown foo(1)? show me what's under hood. thanks!

void main() {        random r = new random();     for(int = 0; < array.length; i++)     {         array[i] = new a(r.next(int.maxvalue));     }         foo(1);      foo(2);     foo(3);  }  a[] array = new a[10000]; static stopwatch sw = new stopwatch();  public void foo(int s) {     sw.reset();     sw.start();      switch(s)     {         case 1:             array.first(x => (x.value == array.max(y => y.value))).dump();             break;         case 2:             array.orderby(x => x.value)             .last()             .dump();                 break;         case 3:             {                            int max = array[0].value;                 int index = 0;                 int = 0;                 for(; < array.length; i++)                 {                     if(array[i].value >= max)                     {                         max = array[i].value;                         index = i;                     }                 }                 array[index].dump();             }             break;     }      sw.stop();     sw.dump(); } class {     public int value;     public a(int value)     {         this.value = value;     } } 

code testing in linqpad, can ignore .dump() method.

the first o(n²), because iterate on array once each outer iteration. second o(n log n), because sorting first. last o(n), because iterate on array in single pass no loop inside each iteration.

try this:

        case 1:             var max = array.max(x => x.value);             array.first(x => x.value == max).dump();             break; 

it should comparable third case, though not quite, since have traverse array 1.5 times, on average (assuming 1 element has max value).