Insertion sort algoritması için elimizde

8 2 1 5 6

gibi bir dizimiz olsun.


Diziyi sıralarken ikinci elemandan yani 2′ den başlıyoruz. Burada 2 ile 8′ i karşılaştırıyoruz ve 2, 8 den küçükse 8′ i, 2′ nin yerine koyuyoruz.

2 yi ise başka karşılaştıracağımız durum oluşmadığı için 8’in yerine koyuyoruz ve son durum ;

2 8 1 5 6

Şimdi ilk başta ikinci elemandan başladığımız için bir artırıp üçüncü elemanı alıyoruz, yani 1 ‘i ;
Sonra 1 i 8 le karşılaştırıyoruz 1, 8 den küçük olduğu için 8, 1 in yerine geçiyor. Ama 1 i daha yerleştirmedik. Sonra 2 ile 1 i karşılaştırıyoruz ve 1 yine küçük olduğu için 2 bu sefer 8 ‘in yerine geçiyor. Ve karşılaştıracak eleman kalmadığı için 1 en başa yerleşir.

1 2 8 5 6

1 2 5 8 6

1 2 5 6 8

Bu sıralama algoritmasının pseudo code’u ise ;

for j = 2 to A.length
     key = A[j]
     // A[j] yi sıralanmış A[1..j-1] ye ekle
     i = j - 1
     while i > 0 ve A[j]> key
          A[i + 1] = A[i]
          i = i - 1
     A[i + 1] = key

Bu sıralama algoritmasının C kodu ise

int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1; 
  
       /* Move elements of arr[0..i-1], that are 
          greater than key, to one position ahead 
          of their current position */
       while (j >= 0 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 

Bu algoritmanın analizine baktığımızda ise ;

En kötü durum için (worst case) n2   dir. (Bütün dizinin tersten sıralanmış hali için)
En iyi durum için (best case) n dir.