Opis metody sortowania przez wstawianie
Ciąg liczb dzielimy na dwie części: posortowaną "S" i nieposortowaną "NS".
Na początku "S" jest puste, a "NS" zawiera całą tablicę.
Bierzemy pierwszy z brzegu element części "NS" i sprawdzamy w które
miejsce części "S" powinien być wstawiony. Oczywiście wymaga to przesunięcia
elementów "S". Część "S" wydłuża się o jeden element, część "NS" traci
jeden element. Z pewnych względów warto przeszukiwanie części "S" zaczynać
od tyłu (dlaczego ?).
"S" || "NS"
1 5 15 95 || 7 3 84 85 86
^ |
| |
--------------------
"S" || "NS"
1 5 7 15 95 || 3 84 85 86
^ |
| |
------------------------------
(i tak dalej ...)