===== Insertion sort =====

Nakon k iteracija pri sortiranju, na početku niza se nalazi sortirani deo niza. Ostatak niza je deo koji tek treba sortirati. Novi element se dodaje na kraj sortiranog dela niza i zatim se poredi sa prethodnim elementom(ako postoji). Ako je novi element manji, oni zamenjuju mesta. Postupak se ponavlja sve dok postoji prethodnik koji je veći.


===Funkcija koja izvršava insertion sort===

<codec>
void isort (int n, int a[]) 
{
  int i,j,k;
  for(i=0; i<n; i++)
    for(j=i; (j>0) && (a[j]<a[j-1]); j--)  
      {
         k=a[j]; 
         a[j]=a[j-1]; 
         a[j-1]=k;
      }
}
</code>

==Primer==
1)Od brojeva 44,55,12,42,94,18,6,67 dobiti sortiran niz pomoću insertion sorta?

pocetak:

44 55 12 42 94 18 6 67

i=1

44 55 12 42 94 18 6 67

i=2

12 44 55 42 94 18 6 67

i=3

12 42 44 55 94 18 6 67

i=4

12 42 44 55 94 18 6 67

i=5

12 18 42 44 55 94 6 67

i=6

6 12 18 42 44 55 94 67

i=7

6 12 18 42 44 55 67 94

[[sortiranje|Nazad]]