[Sorting] IllegalArgumentException in TimSort

Sometimes, simple things like sorting are not simple. We were doing a sorting on a large data set containing around 2000 elements. Sometimes, when most of these elements had null fields, we would get a very weird exception:

Did a bit of googling, and found out this happens when the sorting implementation is not transitive.

The problem that we faced is really, reproducing this consistently, as it seemed to work in most cases and then starts failing seemingly randomly.

In this entry, I will try to reproduce this issue. Let us consider the below entity:

 

We would use the below comparator for sorting this:

 

We will try to sort a List<Person> with the above comparator:

 

This would fail consistently with the below data set:

 

The full test case is here:

https://github.com/paawak/blog/blob/master/code/sort/src/test/java/com/swayam/demo/sort/PersonComparatorNonTransitiveTest.java

Now, consider the below comparator:

 

The difference between the transitive and the non-transitive version is obvious. The real challenge here is having a data-set that fails consistently to cause the exception in TimSort.

The entire source can be found here: https://github.com/paawak/blog/tree/master/code/sort

Leave a Reply

Your email address will not be published. Required fields are marked *