Сортування вставками. 
Порівняння загальних характеристик роботи різних методів сортування

Сортування простими вставками в чомусь схожа на вищевикладені методи.

Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином на його початку «виростає» відсортована послідовність.

Однак у сортуванні бульбашкою або вибором можна було чітко заявити, що на i-му кроці елементи a [0] … a [i] стоять на правильних місцях і нікуди більше не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a [0] … a [i] впорядкована. При цьому по ходу алгоритму в неї будуть вставлятися (див. назву методу) все нові елементи.

Будемо розбирати алгоритм, розглядаючи його дії на i-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a [0] … a [i] і невпорядковану a [i +1] … a [n].

На наступному, (i +1)-м кожному кроці алгоритму беремо a [i +1] і вставляємо на потрібне місце в готову частину масиву.

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

В залежності від результату порівняння елемент або залишається на поточному місці (вставка завершена), або вони міняються місцями і процес повторюється (Рис. 2.10).

Рисунок 2.10 — Процес сортування вставками.

Таким чином, в процесі вставки ми «просіваємо» елемент x до початку масиву, зупиняючись у випадку, коли знайдено елемент, менший x або досягнуто початок послідовності.

Аналогічно сортуванні вибором, середнє, а також найгірше число порівнянь і пересилань оцінюються як Theta (n2), додаткова пам’ять при цьому не використовується.

Хорошим показником сортування є дуже природна поведінка: майже відсортований масив, буде дуже швидко відсортовано. Це, вкупі зі стійкістю алгоритму, робить метод хорошим вибором у відповідних ситуаціях.

Алгоритм можна злегка поліпшити. Зауважимо, що на кожному кроці внутрішнього циклу перевіряються 2 умови. Можна об'єднати з в одне, поставивши в початок масиву спеціальний сторожовий елемент. Він повинен бути свідомо менше всіх інших елементів масиву. Тоді при j = 0 буде свідомо вірно a [0] = 0.

Таким чином, сортування відбуватиметься правильним чином, а у внутрішньому циклі стане на одне порівняння менше. З урахуванням того, що воно проводилося Theta (n2) раз, це — реальна перевага. Однак, відсортований масив буде не повний, так як з нього зникло перше число. Для закінчення сортування це число слід повернути назад, а потім вставити в відсортовану послідовність a [1] … a [n] (Рис. 2.11).

Рисунок 2.11 — Закінчення процесу сортування.