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

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

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

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

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

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

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

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

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

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