Ответ
Timsort — это гибридный, адаптивный, стабильный алгоритм сортировки, сочетающий сортировку вставками (для маленьких подмассивов) и сортировку слиянием.
Ключевые преимущества:
- Адаптивность: Эффективно работает с реальными, часто частично упорядоченными данными. В лучшем случае (уже отсортированный массив) сложность O(n).
- Стабильность: Сохраняет относительный порядок равных элементов, что важно для сортировки по нескольким ключам.
- Гарантированная производительность: Худший и средний случай — O(n log n), что исключает деградацию до O(n²), как у QuickSort в худшем случае.
Где используется:
- Стандартный алгоритм в Python (с
list.sort()иsorted()). - В Java для сортировки объектов (
Arrays.sort()для ссылочных типов,Collections.sort()).
Пример в Java:
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
List<String> names = Arrays.asList("Charlie", "Alice", "Bob");
Collections.sort(names); // Использует Timsort
System.out.println(names); // [Alice, Bob, Charlie]