none
Performance issue with the OrderBy extension method RRS feed

  • General discussion

  • Hi,

    When using a sort function, an overall performance in O(n * log(n)) is usually expected, which is what I have been experiencing with the OrderBy extension method so far.

    But with the test case provided at the end of the message, the algorithm used by the extension method turns out to be quadratic, whereas the Array.Sort method shows the expected, almost linear behaviour.

    Is it a worst case scenario? Can we have some information about the underlying algorithm, so that we know when we should not use the OrderBy extension method?

    Cheers,

    Eric.

    [TestMethod]
    public void Performance_OrderBy()
    {
    	int numberOfRows = 30000;
    	List<int> dataBuilder = new List<int>();
    	for (var i = 1; i < numberOfRows; i += 5)
    	{
    		dataBuilder.Add(i);
    	}
    	for (var i = 3; i < numberOfRows; i += 5)
    	{
    		dataBuilder.Add(i);
    	}
    	int[] data1 = dataBuilder.ToArray();
    	int[] data2 = dataBuilder.ToArray();
    
    	Double seconds1;
    	Double seconds2;
    	var watch = new System.Diagnostics.Stopwatch();
    	watch.Start();
    
    	watch.Restart();
    	Array.Sort(data1);
    	seconds1 = watch.Elapsed.TotalSeconds;
    
    	watch.Restart();
    	var data3 = data2.OrderBy(x => x).ToArray();
    	seconds2 = watch.Elapsed.TotalSeconds;
    
    	Assert.Fail(String.Format("Array.Sort: {0}s, OrderBy: {1}s", seconds1, seconds2));
    }



    Friday, September 7, 2012 8:49 AM

All replies

  • Hi Eric,

    Welcome to the MSDN Forum.

    In my opinion, when sorting a array, you can try Array.Sort. When sorting a list or something else, you need to try Enumerable.orderBy.

    Best regard,


    Mike Feng
    MSDN Community Support | Feedback to us
    Please remember to mark the replies as answers if they help and unmark them if they provide no help.

    Monday, September 10, 2012 7:43 AM
    Moderator
  • Hi Mike,

    Thanks for your answer.
    I have tried to replace the arrays by lists, and I still get the same results: List.sort() is roughly linear, whereas Enumerable.orderBy is quadratic.

    Would it be possible to have more insight on the reason of this discrepancy?

    Regards,

    Eric.

    Monday, September 10, 2012 8:15 AM
  • AFAIK OrderBy uses its own QuickSort implementation and QuickSort can sometimes by n^2 depending on input and implementation.

    List.Sort actually uses Array.Sort. Array.Sort used QuickSort (but a different implementation than the one used by OrderBy) at some point but it seems that now (.NET 4 or 4.5) it has been changed to IntroSort. It also looks like in some cases Array.Sort may use a native implementation.

    Monday, September 10, 2012 8:23 AM
    Moderator