Worst Case Scenario for QuickSort

Take a look at the following code:

    1: var sw = new Stopwatch();

    2: sw.Start();

    3: Enumerable.Range(0, 3).SelectMany((i) => Enumerable.Range(0, 50000)).OrderBy(i => i).ToList();

    4: Console.WriteLine(sw.ElapsedMilliseconds);

    5:  

    6: sw.Reset();

    7: sw.Start();

    8: Enumerable.Range(0, 2).SelectMany((i) => Enumerable.Range(0, 50000)).OrderBy(i => i).ToList();

    9: Console.WriteLine(sw.ElapsedMilliseconds);

   10: sw.Reset();

Line 3 is saying:

Generate a list which looks like 0,1,2..49999,0,1,2..49999,0,1,2..49999

Then Sort it.

While Line 8 is saying:

Generate a list which looks like 0,1,2..49999,0,1,2..49999

Then Sort it.

If you run this program you will see that line 3 executes ( depending on your machine) in less than a second while line 8 executes in around 30 seconds. This may jump out as really strange at first since you are sorting less numbers in line 3.  But that isn't the issue in this scenario. The issue is the sorting algorithm.

Underneath the covers the OrderBy function is using a version of QuickSort.  The version of quicksort used always chooses the middle element of the list as the pivot position.  Since both left and right lists will always be sorted we hit the worst case of this quicksort algorithm which is O(n^2).