Sortowanie przez wstawianie (insertion sort) jest naturalnym algorytmem sortowania. Wielu ludzi stosuje go często, nawet o tym nie wiedząc, chociażby przy układaniu kart w ręce. Sortowanie to jest stabilne, in situ, o złożoności średniej O(n^2). Jest uznawane za najszybsze z sortowań prostych, dodatkowo jest bardzo intuicyjne i nieskomplikowane w implementacji. Nadaj się również do sortowania list. Czasem używa się go w sortowaniu szybkim do sortowania odpowiednio małych przedziałów, co korzystnie wpływa na czas tej operacji.

Sortowanie przez wstawianie (insertion sort) jest stabilnym algorytmem sortowania w miejscu, o kwadratowej złożoności czasowej. Głowne jego zalety to naturalne zachowanie, prostota implementacji i bardzo dobre wyniki dla małych danych wejściowych.

Opis algorytmu

Daną jest tablica, o długości n, oznaczmy: [0, n - 1].

Algorytm ten jest iteracyjny. Zacznijmy od i = 1.
Na początku każdego (i-tego) przebiegu pętli (niezmiennik pętli) mamy tablicę podzieloną na dwie części - posortowaną i nieposortowaną : [0, i - 1], [i, n - 1].
W każdej iteracji wstawiamy pierwszy element z części nieposortowanej, do części posortowanej w odpowiednim miejscu, co powoduje przesunięcie granicy podziału o 1: [0, i], [i + 1, n - 1] (zachowanie niezmiennika).
Jak widać, wystarczy iterować tą pętle dla i od 1 do n, aby cała tablica była posortowana.

Pseudokod

1. procedure insertion_sort(array A)
2. begin
3. for I ← 1 to A.size do
4. begin
5. integer J ← I
6. while J > 0 and A[J] < A[J - 1] do
7. begin
8. A[J] ←→ A[J - 1]
9. J ← J - 1
10 end
11 end
12. end

6. Dopóki I-ty element nie znajduje się na odpowiednim miejscu, zamieniamy go z sąsiadującym elementem, który jest większy od niego. W tym miejscu korzystamy z faktu, że część tablicy od 0 do I - 1 jest posortowana.

Można by pomyśleć, że efektywność tego algorytmu wzrosłaby, gdyby zastosować wyszukiwanie połówkowe, do znalezienia docelowej pozycji dla danego elementu, jednak nie jest to zbyt dobry pomysł, bo i tak musimy przestawić wszystkie elementy, które znajdują się między danym elementem, a miejscem, gdzie powinien się znaleźć.
Dużo lepszą i bardziej ciekawą modyfikacją tego algorytmu jest shell sort, który z drobnymi modyfikacjami może mieć średnią złożoność nawet rzędu O(n lg^2 n).

Implementacja (C/C++)

void insertion_sort(int *tab, int n){
    int i, j, el; 
    for ( i = 1; i < n; ++i ){
	el = tab[i];
	for ( j = i; j > 0 && tab[j - 1] > el; j-- )
	    tab[j] = tab[j - 1];
    }
}

Implementacje (Python)

Według opisu algorytmu:

def insertion_sort1(tab):
    for i in range(len(tab)):
	assert tab[0:i]==sorted(tab[0:i]), 'Naruszenie niezmiennika petli'
	j = i
	while j > 0 and tab[j] < tab[j-1]:
	    tab[j], tab[j-1] = tab[j-1], tab[j]
	    j -= 1

Ponieważ mamy zapewnione, że część tablicy 0:i jest posortowana, możemy przyspieszyć wyszukiwanie miejsca do wstawienia elementu wykorzystując metodę bisekcji i wstawić od razu we właściwe miejsce, zmniejszając liczbę przestawień.

from bisect import insort
def insertion_sort2(tab):
    for i in range(len(tab)):
	assert tab[0:i]==sorted(tab[0:i]), 'Naruszenie niezmiennika petli'
	tmp = tab.pop(i)
	insort(tab, tmp, 0, i)