How Collections.sort() on an ArrayList work internally in JAVA?

We all know that Collections.sort() reduces the developer's effort to manually sort any List. It is always good to know how it works internally.

We will start with the signature of sort() of Collections.java, which goes as below,

According to the documentation, Given that the elements of List are mutually comparable, sort method modifies the list into ascending order based on comparable natural ordering of its elements. The sort is guaranteed to be stable which means objects with the same values are not reordered. The list which is passed as parameter should be modifiable and not necessarily resizable.

For the sake of easy understanding, we will go with the ArrayList as it is a very commonly used implementation of List type.

ArrayList’s implementation of sort utilizes Arrays.sort() method ,below is its its implementation.

When the size of the list is <=64 it uses binary insertion sort which offers the best performance for a small number of elements. For the lists having more than 64 elements, It uses stable, adaptive and iterative merge sort which is adapted from Tim Peters’s list sort, it needs less than nlogn comparisons for a partially sorted list and it also offers a performance of traditional merge sort for a randomly ordered list.

So to conclude when we invoke Collections.sort() on an ArrayList, in its implementation, it invokes Arrays.sort() which utilises iterative merge sort technique to sort the elements in their natural ascending order.