Is .NET 4.5 introspective implementation of Array.Sort deterministic?

Question

.NET 4.5 changed the implementation of Array.Sort to what is called "introspective sort" which is a hybrid algorithm, consisting of choosing between quicksort, insertionsort, and heapsort depending on the input data. It is detailed here:

http://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx

It is well documented that the sort is "unstable", meaning two elements containing the same sort order value may or may not preserve the order from the original input. However, I need to know whether or not it is "deterministic", in the sense that any arbitrary input data will reproducibly return the same output data every time it is sorted. Specifically, I know that quicksort can be implemented either deterministically or non-deterministically (if the pivot is chosen at random), but I'm not sure which implementation is used for .NET's introspective sort.

From my testing, it seems to be deterministic, as I have not seen any particular set of data return differently between runs, but obviously you can't prove something doesn't exist simply because you haven't seen it :-/

I suppose I plan on looking at the code to help try to figure out whether or not introspective sort is deterministic, but I was hoping that someone here knows offhand and can save me the effort ;)

Thanks! Ryan

Answer 1

Unfortunately, someone basically relied on it being deterministic in 4.0, and now that we have upgraded we are finding discrepancies. What we'd like to do is compile against 4.0 and resort the same sets to get back what we were getting, we just want to make sure that when we do that, we can rely on the sorts being the same as they previously were. In other words, is the quicksort implementation Array.Sort in 4.0 deterministic?

So you want to find out for a particular version whether Array.Sort is deterministic. That is a much easier problem.

Decompile the .NET BCL code (or look at the reference source). If the implementation is using only deterministic operations (i.e. not using Random) the result is also deterministic.

Last time I looked the sorting code fit onto just a few pages. You'll quickly sift through it. My guess: It will obviously be deterministic (if your comparer is as well!).