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

Сортування злиттям — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй».
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так доти, доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме доти, доки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

Класифікація методів сортування

Сортування стало важливим предметом обчислювальної математики в основному тому, що воно займає значну частину часу роботи програм – близько 25% всього часу обчислень витрачається на сортування даних. Сортування також є важливим засобом для прискорення роботи майже будь-якого алгоритму, в якому потрібно часто звертатися до певних елементів.Більшість програм, які використовують методи сортування віддають перевагу найпростішим алгоритмам. По-перше, дуже часто програма сортування використовується лише один або кілька разів. Після того, як вдалося вирішити «проблему» сортування для певного набору даних, в подальшому необхідність в сортуванні, в програмах, які маніпулюють цими даними, відпадає. Якщо елементарне сортування працює не повільніше ніж 

інші частини програми, що виконують обробку даних, то відпадає необхідність пошуку швидших методів сортування. Якщо кількість елементів, що сортуються, не дуже велика (до кількох сотень), можна просто скористатися простим методом і не ламати голову над тим, як працює інтерфейс для системного сортування, або як написати і налагодити програму,  що реалізує який-небудь складний метод сортування. По-друге, елементарні методи завжди підходять для наборів невеликих розмірів (до кількох десятків елементів) – складні алгоритми, в загальному випадку, супроводжуються додатковими затратами ресурсів. Це призводить до того, що на наборах малих розмірів вони працюють повільніше елементарних методів сортування. Це нас не турбуватиме доти, доки не виникне необхідність сортування великої кількості наборів невеликих розмірів. Іншими типами наборів, сортування яких значно спрощене, є набори з майже завершеним упорядкуванням, або набори, які містять велику кількість однакових даних.

Класифікація методів сортування

 за принципом роботи:

–адаптивні - сортування виконує різні послідовні операції в залежності від результатів порівняння;

–неадаптивні - послідовність операцій, які вони виконують, не 

залежить від порядку слідування даних (наприклад:

бульбашковий, метод вставок та метод вибору).

Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний: Ця функція набагато коротше нерекурсивної функції, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції". Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.

Аналіз алгоритму