InsertionSortSpiegato

Insertion_Sort(array A[])
n=lenght(A)  //Prendo la lunghezza della sequenza
for j=2 to n do //itero dalla posizione j=2 fino a tutta la sequenza
	key=A[j] //assegno a una variabile key (come tmp) il valore nella mia "j" posizione, ovvero la 2 per cominciare
	i=j-1 //decremento l'indice i alla posizione j-1 ovvero 2-1 = 1 -> posizione 1
	while(i>0 && A[i]>key)do //se la i>0 e l'elemento dell'array in posizione A[i] è maggiore della key presa prima
		A[i+1]=A[i] //swap della posizione successiva con l'elemento precedente
		i=i-1 //decremento lo scorrimento di i quindi se era uguale a 1 prima ora sarà 1-1 = 0
	A[i+1]=key //assegno ad A[i+1] il valore della key precedente.
return A //ritorno l'array