Sortowanie przez wstawianie .

• Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii.

Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii.
Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego).
Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. Insertion Sort).
Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu. Tak porządkujemy karty.
A jak przenieść tę ideę do świata komputerów i zbiorów liczbowych?

• Algorytm sortowania przez wstawianie będzie składał się z dwóch pętli.

Pętla główna (zewnętrzna) symuluje pobieranie kart, czyli w tym wypadku elementów zbioru.
Odpowiednikiem kart na ręce jest tzw. lista uporządkowana (ang. sorted list), którą sukcesywnie będziemy tworzyli na końcu zbioru (istnieje też odmiana algorytmu umieszczająca listę uporządkowaną na początku zbioru).
Pętla sortująca (wewnętrzna) szuka dla pobranego elementu miejsca na liście uporządkowanej.
Jeśli takie miejsce zostanie znalezione, to elementy listy są odpowiednio rozsuwane, aby tworzyć miejsce na nowy element i element wybrany przez pętlę główną trafia tam.
W ten sposób lista uporządkowana rozrasta się.
Jeśli na liście uporządkowanej nie ma elementu większego od wybranego, to element ten trafia na koniec listy.
Sortowanie zakończymy, gdy pętla główna wybierze wszystkie elementy zbioru.