Сортування злиттям
Сортування злиттям — інтерактивний експеримент із застосунку «Алгоритми в дії», безкоштовної симуляції StudyFi Lab, яка працює просто в браузері.
Сортування злиттям ділить масив навпіл, упорядковує кожну половину тим самим способом (рекурсія), а потім зливає дві впорядковані половини: завжди бере менший із двох перших елементів. Ділення навпіл дає log₂ n рівнів, і на кожному рівні обробляються всі n елементів, тому час завжди O(n log n). У разі рівності береться лівий елемент, тому сортування стійке.
Спробуй: Спробуй зворотний, а потім майже впорядкований масив того самого розміру. Кількість порівнянь майже не змінюється — порядок вхідних даних майже не важливий.
Поширені запитання
Що показує експеримент «Сортування злиттям»?
Сортування злиттям ділить масив навпіл, упорядковує кожну половину тим самим способом (рекурсія), а потім зливає дві впорядковані половини: завжди бере менший із двох перших елементів. Ділення навпіл дає log₂ n рівнів, і на кожному рівні обробляються всі n елементів, тому час завжди O(n log n). У разі рівності береться лівий елемент, тому сортування стійке.
Як спробувати «Сортування злиттям»?
Спробуй зворотний, а потім майже впорядкований масив того самого розміру. Кількість порівнянь майже не змінюється — порядок вхідних даних майже не важливий.
Готуєшся до контрольної?
Завантаж свої конспекти, і StudyFi перетворить їх на картки, тести й подкасти.