Bad sorting and other pitfalls

time to read 1 min | 194 words

While tracing a bug, I ended up with the following minimum reproduction:

The error you’ll get is:

Unable to sort because the IComparer.Compare() method returns inconsistent results. Either a value does not compare equal to itself, or one value repeatedly compared to another value yields different results.

The nasty thing about this is that if we had just 16 items in the array, this code would work. So this would appear to successfully work most times, and then break.

The underlying issue is that Array.Sort will use different sorting algorithms based on the size of the array to be sorted. Under 16 items, it’ll use an insertion sort, but over that, an introspection sort will be used (up to a limit, and then heap sort. Go read the code.).

What is key here is that our comparison function is broken. It doesn’t understand that two values can be equal. Because of that, comparing two equal values result in both of them being smaller than one another. That cause an error, and .NET issues this error. When you know what went wrong, the fix is pretty easy:

Now we properly handle this scenario, and everything will work.