Algorytmy i struktury danych · Middle · Pytanie 2 z 75
Jaka jest główna wada sortowania przez scalanie na tablicach?
- 1Ma O(n²) na już posortowanych danych
- 2Nie jest stabilne, więc równe klucze się przestawiają
- ✓Poprawna odpowiedź: Potrzebuje O(n) dodatkowej pamięci na scalanie
Wyjaśnienie
Krok scalania zapisuje do tymczasowego bufora. Czas to O(n log n) niezależnie od danych, a klasyczna implementacja jest stabilna. Na listach wiązanych scalanie da się zrobić bez dodatkowego bufora.