Загальна схема алгоритму
Метод сортування злиттям масиву складається з двох великих етапів:
- Розділити неотсортированный вихідний масив на маленькі частини.
- Зібрати їх попарно, дотримуючись правило сортування.
Велика і складна задача тут розбивається на багато простих, які послідовно вирішуються, приводячи до бажаного результату.
Оцінка роботи методу
Тимчасова складність сортування злиттям визначається висотою дерева розбиття алгоритму і дорівнює кількості елементів у масиві (n), помноженому на його логарифм (log n). Така оцінка називається логарифмічною.
Це одночасно і перевага, і недолік методу. Час його роботи не змінюється навіть у гіршому випадку, коли вихідний масив відсортований в зворотному порядку. Однак при обробці повністю відсортованих даних алгоритм не забезпечує виграш у часі.
Важливо відзначити і витрати пам’яті при роботі методу сортування злиттям. Вони дорівнюють розміру вихідної колекції. У цій додатково виділеної області з шматочків збирається відсортований масив.
