Асимптотичен анализ и сравнение на алгоритми за сортиране
Добре установен факт е, че сортирането чрез сливане работи по-бързо от сортирането чрез вмъкване. Използване на асимптотичен анализ. можем да докажем, че сортирането чрез сливане се изпълнява за O(nlogn) време, а сортирането чрез вмъкване отнема O(n^2). Очевидно е, защото сортирането чрез сливане използва подход "разделяй и владей" чрез рекурсивно решаване на проблемите, където сортирането чрез вмъкване следва постепенен подход. Ако разгледаме още повече анализа на времевата сложност, ще разберем, че сортирането с вмъкване не е толкова лошо. Изненадващо сортирането чрез вмъкване е по-добро от сортирането чрез сливане при по-малък входен размер. Това е така, защото има няколко константи, които пренебрегваме, докато извеждаме времевата сложност. При по-големи входни размери от порядъка на 10^4 това не влияе на поведението на нашата функция. Но когато входните размери паднат под, да кажем по-малко от 40, тогава константите в уравнението доминират над входния размер „n“. Дотук добре. Но не бях доволен от такъв математически анализ. Като студент по компютърни науки трябва да вярваме в писането на код. Написах програма на C, за да усетя как алгоритмите се конкурират един срещу друг за различни входни размери. И също защо се прави такъв строг математически анализ за установяване на сложността на времето за изпълнение на тези алгоритми за сортиране.
