Idea tego algorytmu polega na sukcesywnym wstawianiu kolejnych elementów na właściwą pozycję w już uporządkowanym fragmencie ciągu. Dokładniej, sortowanie odbywać się będzie w n-1 etapach. W i-tym etapie zapamiętujemy i-ty element i porównujemy go z elementami poprzedzającymi. W przypadku, gdy są one większe niż i-ty, zostaną przesunięte o jedno miejsce w prawo zwalniając w ten sposób zajmowaną pozycję i robiąc ew. miejsce dla elementu i-tego. Zauważmy, że w wyniku przesunięć nie "zgubiliśmy, żadnego elementu, bo element i-ty został na początku zapamiętany na zmiennej pomocniczej pom. W ten sposób zwolniła się pozycja i-ta i mogliśmy na niej umieścić element z pozycji sąsiedniej, itd. Przesunięcia w prawo kontynuujemy tak długo, aż znajdziemy element, który jest mniejszy bądź równy elementowi i-temu i wówczas wpisujemy element zapamiętany na wolną pozycję z jego prawej strony (por. Rysunek 4.2).

Algorytm realizujący opisaną wyżej ideę nosi nazwę sortowania przez wstawianie (InsertionSort). Zauważmy, że strategia postępowania jest w tym algorytmie inna niż w algorytmie SelectionSort. Tam nigdy nie wracaliśmy do elementów, które wcześniej zostały wybrane. Natomiast wielokrotnie przeglądaliśmy elementy, które tworzyły blok elementów jeszcze nieuporządkowanych. Tu odwrotnie. Z segmentu nieuporządkowanego bierzemy po jednym elemencie i wstawiamy go na właściwą pozycję w segmencie uporządkowanym "przepychając", jeśli trzeba, elementy większe, już uporządkowane, o jedną pozycję w prawo.

InsertionSort (e : ciąg){
	i := 2; n := e.length;
	while (i £ n) do	// e[1] £...£ e[i-1], i £ n+1 oraz i £ n
	j := i; pom := e[i];	// e[i] = pom
	while (j>1 and e[j-1]>pom) do	// pom £ e[j+1] £ ... £ e[i] oraz e[j-1]>pom
	e[j] := e[j-1];	// pom £ e[j] £ e[j+1] £ ... £ e[i]
	j := j - 1;	// pom £ e[j+1] £ ... £ e[i]
	od;	// e[1] £...£ e[j-1] £ pom £ e[j+1] £ ... £ e[i]
	e[j] := pom;	// e[1] £...£ e[i-1] £ e[i]
	i := i+1;	// e[1] £...£ e[i-2] £ e[i-1], i £ n+1
	od
}		// e[1] £...£ e[i-2] £ e[i-1] oraz i=n+1

Niech e₁, ..., e_n będzie ciągiem, którego elementy stanowią początkowe wartości tablicy e oraz n>0, czyli spełniony jest warunek początkowy specyfikacji algorytmów sortowania. Mamy wykazać, że po wykonaniu algorytmu spełniony będzie także warunek końcowy

wk = {e[1] £ e[2] £ ... £ e[n] oraz istnieje taka permutacja i₁, ..., i_n liczb 1,..., n, e[1] = e_i1, e[n]= e_in }.

Rozważymy najpierw pętlę wewnętrzną. Załóżmy, że wszystkie elementy od pozycji 1 aż do pozycji i-1 zostały już uporządkowane i wchodzimy do pętli wewnętrznej "while" wiedząc, że wszystkie elementy na pozycjach od j+1,..., i są większe od elementu pom. Przed pierwszym wejściem do pętli wewnętrznej tak właśnie jest, bo j=i. Jeśli warunek pętli wewnętrznej jest spełniony, to prawdziwe są własności:

Zatem przesuwając na pozycję j-tą element e[j-1], otrzymamy pom £ e[j] £ e[j+1] £ ... £ e[i]. Po wykonaniu przypisania "j:= j-1;", ponownie prawdziwa jest własność

Ta ostatnia formuła jest więc niezmiennikiem pętli "while (i £ n) ". Na mocy twierdzenia o niezmiennikach (por. wykład I, p.4), po wykonaniu pętli wewnętrznej spełniony jest niezmiennik oraz, albo j=1, albo e[j-1]£ pom. Ponieważ żadna z pozycji e[1] do e[j-1] nie została w tej pętli zmieniona, zatem, korzystając z założenia i z niezmiennika możemy w obu przypadkach stwierdzić, że prawdziwa jest formuła

Zauważmy jeszcze, że aktualne wartości e[1],...,e[j-1], pom, e[j+1],...,e[i] są permutacją oryginalnych wartości danego ciągu e₁, ..., e_i.

Jeśli w kolejnej iteracji pętli zewnętrznej spełniony jest warunek pętli (i £ n) oraz formuła (*), to na mocy poprzednich rozważań, po wykonaniu pętli wewnętrznej mamy e[1] £...£ e[j-1] £ pom £ e[j+1] £ ... £ e[i]. Wstawiając na miejsce j-te zapamiętany wcześniej na zmiennej pom element e[i], otrzymujemy e[1] £...£ e[i-1] £ e[i]. Ponadto nadal (i £ n). Po zmianie wartości i, mamy e[1] £...£ e[i-1] Ù i £ n+1.

Ponieważ formuła (*) jest prawdziwa trywialnie przy pierwszym wejściu i w każdej iteracji pętli zewnętrznej, to jest również prawdziwa w chwili wyjścia. Zewnętrzna pętla zakończy się, gdy i >n, co łącznie z formułą (*) daje e[1]£...£e[n]. Ponieważ w i-tym kroku, wartości pierwszych i elementów stanowią permutację pierwszych i elementów danego ciągu e₁, ..., e_i, zatem po zakończeniu pętli zewnętrznej elementy tablicy e są permutacją elementów danego ciągu.

Twierdzenie 2.1 Algorytm InsertionSort jest całkowicie poprawnym rozwiązaniem problemu sortowania, w każdej strukturze danych z liniowym porządkiem £.

Zastanówmy się najpierw nad przypadkami szczególnymi. Załóżmy że dany ciąg, do którego chcemy zastosować algorytm InsertionSort jest już uporządkowany niemalejąco. Wykonanie pętli wewnętrznej za każdym razem zakończy się na zbadaniu warunku (j>1 and e[j-1]>pom). Żaden element nie będzie przesunięty. W każdej iteracji zewnętrznej pętli, wykonamy więc tylko jedno porównanie. Razem n-1 porównań.

A jak się zachowa nasz algorytm w przypadku ciągu odwrotnie uporządkowanego? Każdy element trzeba będzie przenieść na pozycję pierwszą. Ale w tym celu pętla wewnętrzna będzie musiała przesunąć cały już uporządkowany fragment o jedno miejsce w prawo, wykonując w i-tym kroku i-1 porównań. Razem 1 + 2 + ...+ n-1 porównań. Przypadek tu rozpatrywany jest najgorszy dla algorytmu InsertionSort, zatem koszt czasowy pesymistyczny wynosi W(n) = n(n-1)/2.

A jaki jest średni koszt czasowy algorytmu? W pętli zewnętrznej nie wykonujemy porównań. Policzymy więc jaka jest oczekiwana liczba porównań wykonanych przez pętlę wewnętrzną. W i-tym kroku mamy już uporządkowane elementy na pozycjach e[1],...,e[i-1], a zadanie pętli wewnętrznej polega na wstawieniu elementu e[i] na jedną z pozycji 1,2,...,i. Załóżmy, że z takim samym prawdopodobieństwem element e[i] może zająć każde z tych i miejsc. Zatem prawdopodobieństwo, że e[i] zajmie miejsce j-te wynosi 1/i. Jeśli e[i] ma trafić na miejsce j-te, to musieliśmy element e[i] porównać z e[i-1],..., e[j], e[j-1] wykonując przy tym i-j+1 porównań. Wynika stąd, że średni liczba porównań wykonanych przez pętlę wewnętrzną wynosi

A(n) = S _i=2,...,n (średnia liczba porównań wykonanych w i-tym kroku algorytmu) = S _i=2,...,n (i+1)/2 .

Ostatecznie A(n) = (1/4)n² +O(n). Koszt średni algorytmu InsertionSort niewiele odbiega od kosztu w przypadku pesymistycznym: też jest kwadratowy.

Algorytm sortowania przez wstawianie sortuje w miejscu, tzn. wykorzystuje tylko pamięć konieczną do przechowywania danych i kilka zmiennych pomocniczych. Jego koszt pamięciowy jest więc liniowy w stosunku do rozmiaru danych, S(n) = Q(n)

Niech dany ciąg składa się z liczb całkowitych, 4,2,6,1,7,5. Stany tablicy e w kolejnych iteracjach pętli zewnętrznej algorytmu InsertionSort są następujące:

4,2,6,1,7,5 2,4,6,1,7,5 2,4,6,1,7,5 1,2,4,6,7,5 1,2,4,6,7,5 1,2,4,5,6,7.

Pytanie 2: Algorytm InsertionSort wykonuje dość dużo instrukcji przypisania. Policzmy tylko te, które dotyczą elementów ciągu. Ile ich wykonamy w przypadku pesymistycznym, jeżeli ciąg składa się z n elementów?