2

.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

Improve this question
4
  • No, that's what "unstable" means. If the equality comparer isn't sufficiently selective then arbitrary input data does not reproducibly sort in the same order. Commented Feb 28, 2014 at 17:54
  • 1
    If it's not documented on the Array.Sort page that the algorithm is deterministic, is is very risky to rely on it. After all, you just saw 4.5 change the algorithm. It can change again. Commented Feb 28, 2014 at 20:14
  • 1
    HansPassant - what I mean is that it will be repeatedly sort in the same order, given the same input (for any arbitrary input). @usr - 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? Commented Feb 28, 2014 at 21:11
  • @user3365745 Good point, just because it's unstable, doesn't mean it's undeterministic. Commented Sep 25, 2014 at 10:28

1 Answer 1

Reset to default
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!).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Yes you are correct. I will take a look, and report back with my findings.
After review, the sort does indeed appear to be deterministic. I reviewed the Sort code here as well as found a similar SO question here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.