Complexidade de tempo do Collections.sort()

Olá Rodrigo, tudo bem com você?

Isso depende da versão do Java; até o Java 6, era utilizado um Merge sort modificado, onde o desempenho linearitmico O(n log n) era garantido. De acordo com a documentação do Java 6:

O algoritmo de ordenação é um mergesort modificado (no qual a fusão é omitida se o elemento mais alto na sublista inferior for menor do que o elemento mais baixo na sublista alta). Este algoritmo oferece desempenho n log (n) garantido. [...] Essa implementação copia a lista especificada em uma matriz, ordena a matriz e itera sobre a lista, redefinindo cada elemento da posição correspondente na matriz. Isso evita o desempenho n 2 log (n) que resultaria da tentativa de classificar uma lista encadeada.

No Java 7, aperfeiçoaram o método e agora o Timsort é utilizado em seu lugar. Ele é um híbrido derivado do Merge sort e do Insertion sort que requer muito menos comparações que n log(n) quando a lista está parcialmente ordenada, ao mesmo tempo que mantém a mesma performance do Merge sort em listas aleatórias e na análise de pior caso.

Nota de implementação: esta implementação é um mergesort estável, adaptável e iterativo que requer muito menos do que n log (n) comparações quando o array de entrada está parcialmente ordenado, enquanto oferece o desempenho de um mergesort tradicional quando o array de entrada está ordenado aleatoriamente. Se a matriz de entrada estiver quase ordenada, a implementação requer aproximadamente n comparações. Os requisitos de armazenamento temporário variam de uma pequena constante para matrizes de entrada quase ordenadas a n / 2 referências de objeto para matrizes de entrada ordenadas aleatoriamente.

Muito obrigado pela resposta completíssima, Thiago!