Ответ
Начиная с Java 7, метод Collections.sort() (и List.sort()) для сортировки объектов использует TimSort — гибридный, устойчивый алгоритм сортировки.
Характеристики TimSort:
- Гибрид: Комбинация сортировки слиянием (MergeSort) и сортировки вставками (InsertionSort).
- Устойчивость (Stable): Не меняет порядок равных элементов, что важно при сортировке по нескольким ключам.
- Сложность: O(n log n) в худшем и среднем случае, O(n) в лучшем (для уже частично отсортированных данных).
- Оптимизация: Эффективно работает с реальными, часто частично упорядоченными данными.
Пример:
import java.util.*;
List<String> names = Arrays.asList("Zoe", "Alice", "Bob", "Charlie");
Collections.sort(names); // Используется TimSort
System.out.println(names); // [Alice, Bob, Charlie, Zoe]
// С компаратором также используется TimSort
Collections.sort(names, Comparator.reverseOrder());Важное отличие: Метод Arrays.sort() для массивов примитивов (например, int[]) использует Dual-Pivot Quicksort. Для массивов объектов также используется TimSort.
int[] numbers = {5, 1, 4, 2};
Arrays.sort(numbers); // Dual-Pivot Quicksort для примитивов
String[] words = {"Zoe", "Alice"};
Arrays.sort(words); // TimSort для объектов