Алгоритми та структури даних · Middle · Запитання 4 з 75
Чому швидке сортування на практиці часто швидше за злиття, хоча в середньому обидва O(n log n)?
- 1Воно стабільне, тож не переміщує рівні елементи
- 2Воно робить менше порівнянь у найгіршому разі
- ✓Правильна відповідь: Воно сортує на місці й звертається до пам'яті послідовно
Пояснення
Розбиття працює всередині масиву з доброю локальністю кешу й малими константами. Його найгірший випадок насправді гірший (O(n²)), а звичайна версія на місці нестабільна.