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