INSERTION SORT

E' uno dei più semplici modi di ordinare un array. Un esempio di insertion sort occorre nella vita di ogni giorno mentre giochiamo a carte. Per ordinare le carte nelle tue mani estrai una carta, "scala" le carte rimanenti, e inserisci la carta estratta nel posto corretto. Questo processo è ripetuto finchè tutte le carte sono nella sequenza corretta.
Il metodo di ordinamento ad inserzione trae lo spunto dall'idea che un vettore ordinato si ottiene inserendo le sue componenti una per una "al posto giusto". Non si introduce un secondo vettore, ma si "simula" l' inserzione degli elementi nel vettore dato.
Sia il caso medio che il peggiore caso hanno complessità O(n²). Nel caso migliore (vettore ordinato) bastano n-1 confronti.
Assumendo che ci siano n elementi nell'array, dobbiamo scorrere n-1 elementi. Per ogni elemento, occorre esaminare e shiftare giù altri n-1 elementi, per cui risulta una complessità O(n²).
Insertion sort è un algoritmo di sort in-place (ordiniamo l'array senza che altra memoria sia necessaria).
Insertion sort è di tipo stable (se ci sono elementi identici mantengono il loro posto originale senza essere ordinati).

ESEMPIO

In figura a), estraimo il 3. Poi gli elementi superiori sono shiftati giù fino a trovare il posto giusto per inserire il 3.
 
 

In figura b) si ripete lo stesso processo di figura a).
 
 

In figura c) completiamo l'ordinamento inserendo il 2 nel posto giusto.