СР 7 Сортування злиттям


Дія алгоритму на прикладі сортування випадкових точок.

Сортування злиттям ( англ. merge sort ) — Алгоритм сортування, який впорядковує списки (або інші структури даних, доступ до елементів яких можна отримувати тільки послідовно, наприклад — потоки) в певному порядку. Ця сортування — гарний приклад використання принципу » розділяй і володарюй «. Спочатку завдання розбивається на декілька підзадач меншого розміру. Потім ці завдання вирішуються за допомогою рекурсивного виклику або безпосередньо, якщо їх розмір досить малий. Нарешті, їх рішення комбінуються, і виходить рішення вихідної задачі.

Приклад сортування злиттям. Спочатку ділимо список на шматочки (по 1 елементу), потім порівнюємо кожен елемент з сусіднім, сортуємо і об’єднуємо. У підсумку, всі елементи відсортовані і об’єднані разом.

Для вирішення завдання сортування ці три етапи виглядають так:

  1. Сортований масив розбивається на дві частини приблизно однакового розміру;
  2. Кожна з вийшов частин сортується окремо, наприклад — тим же самим алгоритмом;
  3. Два впорядкованих масиву половинного розміру з’єднуються в один.

1.1. — 2.1. Рекурсивне розбиття задачі на менші відбувається до тих пір, поки розмір масиву не досягне одиниці (будь масив довжини 1 можна вважати впорядкованим).

3.1. З’єднання двох упорядкованих масивів в один.
Основну ідею злиття двох відсортованих масивів можна пояснити на наступному прикладі. Нехай ми маємо два подмассіва. Нехай також, елементи подмассіва в кожному з цих подмассіва відсортовані за зростанням. Тоді:
3.2. Злиття двох подмассівів в третій результуючий масив.
На кожному кроці ми беремо менший із двох перших елементів подмассіва і записуємо його в результуючий масив. Лічильники номерів елементів результуючого масиву і подмассіва з якого був узятий елемент збільшуємо на 1.
3.3. «Причеплення» залишку.
Коли один з подмассіва закінчився, ми додаємо всі залишилися елементи другого подмассіва в результуючий масив.