Why does the .NET Sort algorithm request a comparison of elements with itself?

Question

I noticed that when sorting an array in .NET using a custom IComparer<T> queries are executed to map the element to itself.

Why is this so? Of course, this is a trivial optimization to see if the comparison should consist of identical indices, and to assume that the result should be zero?

Code example:

 class Comparer : IComparer<string> { public int Compare(string x, string y) { Console.WriteLine("{0} vs {1}", x, y); return string.Compare(x, y); } } static void Main(string[] args) { var values = new[] {"A", "D", "C", "B", "E"}; Array.Sort(values, new Comparer()); } 

With an exit (strange comparisons are noted):

 A vs C A vs E C vs E A vs C D vs C C vs E C vs B C vs C *** C vs C *** A vs B A vs B A vs A *** A vs B A vs A *** D vs E D vs E D vs D *** D vs E D vs D *** 

Answer 1

People report different results because the Array.Sort () algorithm has been modified several times. At least in .NET 4.0 and again in .NET 4.5, perhaps before that. The latest and greatest version has switched from QuickSort to Introsort.

You see an element that compares on its own due to a countermeasure against Quicksort's very poor worst case behavior, O (n ^ 2). The Wikipedia article for Introsort explains well:

In quicksort, one of the critical operations is pivot point selection: the element around which the list is broken. The easiest algorithm for selecting control points is to take the first or last element of the list as a rotation, which leads to poor behavior for the case of sorted or almost sorted input. The Niklaus Wirth variant uses a middle element to prevent these cases, degenerating to O (n²) for contrived sequences. The median-3 reference points selection algorithm accepts the median of the first, middle, and last list items; however, while this works well on many real inputs, you can still create a list of 3 median killers that will drastically slow down quick sorting based on this selection technique. Such inputs could potentially be used by the aggressor, for example, by sending such a list to the Internet server for sorting as an attack on denial of service.

You see the side effects of the median-of-3 rotation selection algorithm.