Алгоритми та структури даних · Senior · Запитання 31 з 75
Чому Timsort такий швидкий на реальних даних?
- 1Він переходить на сортування підрахунком для чисел
- ✓Правильна відповідь: Він знаходить уже відсортовані серії й зливає їх
- 3Він сортує паралельно на всіх ядрах процесора
Пояснення
Реальні дані часто частково впорядковані: дописані логи, майже відсортовані списки. Timsort знаходить зростаючі (або розвернуті спадні) серії, доповнює короткі вставками й зливає їх із «галопом», наближаючись до O(n) на майже відсортованих даних.