Оцінка часу роботи
Очевидно, що в найкращому випадку на вході алгоритму буде вже впорядкований правильним чином масив. У цій ситуації алгоритмом доведеться просто перевірити кожний елемент, щоб переконатися, що він стоїть на своєму місці, не здійснюючи обмінів. Таким чином, час роботи буде прямо залежати від довжини вихідного масиву O(n).
Найгірший випадок вхідних даних – масив, відсортований у порядку, зворотному до потрібного. Тут потрібна велика кількість перестановок, функція часу виконання буде залежати від кількості елементів, зведеного в квадрат.
Точна кількість перестановок для абсолютно неупорядкованого масиву можна обчислити за формулою:
n*(n-1)/2
, де n – довжина вихідного масиву. Таким чином, для розстановки 100 елементів у правильному порядку потрібно 4950 перестановок.
Метод вставок дуже ефективний для сортування невеликих або частково впорядкованих масивів. Однак повсюдно застосовувати його не рекомендується із-за високої складності обчислень.
Алгоритм використовується як допоміжний у багатьох інших більш складних методах сортування.
