Karışık düzende verilmiş bir dizide ilk sıradan başlamak üzere her bir değeri olması gereken yere yerleştirme şeklinde çalışır. Sıralanacak veri setinin ilk elemanının yerinde bırakılması ve sırayla sonraki elemanların teker teker alınıp öncekilerin diziliminde uygun olacak yere konulması ile yapılan işlemdir. İlk eleman kendi yerinde bırakılır. Sonrasında ikinci eleman birincisi ile karşılaştırılarak önüne veya ardına yerleştirilir. Sonraki eleman alınır. Sıralanmış dizi içerisinde uygun olan yere ( en öne, aralarına veya en sona) yerleştirilir. Bu işlem tüm elemanlar için gerçekleştirilerek sıralama işlemi yapılır.
Şöyle ki, sıralanacak olan dizi iki parçaya bölünür. Bir taraf sıralı parçadır. Diğer taraf ise sırasız parçadır. Programlaması oldukça basit bir algoritmadır. Ancak performans açısında çok hızlı olduğu söylenemez. Çünkü sıralanmış kısımda araya sokulacak elemanın yerini bulma ve kalanları kaydırma işlemleri gerekir. n elemanlı karışık bir dizinin çözümü n-1 adımda gerçekleşir. Aslında bu algoritma sıralı olan herhangi bir dizi içerisine sıralı olma durumunu bozmadan yeni elemanlar eklemek için uygundur. Sıralı bir dizide bu algoritma ile yeni bir eleman eklemenin zaman karmaşıklığı O(n) dir. Sıralı olmayan bir dizide bu algoritma ile yeni bir eleman eklemenin zaman karmaşıklığı ise O(n²) dir.
Sıralanması nı istediğimiz dizi “9 4 5 3 2 1 8 6 7” olsun.
Dizimizin ilk hali 
Aşağıda adım adım işlemler sıralanmaktadır.
9 rakamı ilk eleman olduğu için olduğu yerde bırakıyoruz.
4 sayısı için uygun yeri arıyoruz. 4 sayısı 9 un yerine geçmelidir. Bu nedenle 9 ve 9’dan sonraki tüm sıralanmış elemanlar bir adım sağa doğru boşluğu dolduracak şekilde ilerletilir. 4 sayısı boşalan yere geçer.
5 sayısı için uygun yeri arıyoruz. 5 sayısı 9 un yerine geçmelidir. Bu nedenle 9 ve 9’dan sonraki tüm sıralanmış elemanlar bir adım sağa doğru boşluğu dolduracak şekilde ilerletilir. 5 sayısı boşalan yere geçer.
3 sayısı için uygun yeri arıyoruz. 3 sayısı 4 un yerine geçmelidir. Bu nedenle 4 ve 4’ten sonraki tüm sıralanmış elemanlar bir adım sağa doğru boşluğu dolduracak şekilde ilerletilir. 3 sayısı boşalan yere geçer.
2 sayısı için uygun yeri arıyoruz. 2 sayısı 3 ün yerine geçmelidir. Bu nedenle 3 ve 3’ten sonraki tüm sıralanmış elemanlar bir adım sağa doğru boşluğu dolduracak şekilde ilerletilir. 2 sayısı boşalan yere geçer.
1 sayısı için uygun yeri arıyoruz. 1 sayısı 2 nin yerine geçmelidir. Bu nedenle 2 ve 2’den sonraki tüm sıralanmış elemanlar bir adım sağa doğru boşluğu dolduracak şekilde ilerletilir. 1 sayısı boşalan yere geçer.
8 sayısı için uygun yeri arıyoruz. 8 sayısı 9 un yerine geçmelidir. Bu nedenle 9 ve 9’dan sonraki tüm sıralanmış elemanlar bir adım sağa doğru boşluğu dolduracak şekilde ilerletilir. 9 sayısı boşalan yere geçer.
6 sayısı için uygun yeri arıyoruz. 6 sayısı 8 nin yerine geçmelidir. Bu nedenle 8 ve 8’den sonraki tüm sıralanmış elemanlar bir adım sağa doğru boşluğu dolduracak şekilde ilerletilir. 6 sayısı boşalan yere geçer.
7 sayısı için uygun yeri arıyoruz. 7 sayısı 8 nin yerine geçmelidir. Bu nedenle 8 ve 8’den sonraki tüm sıralanmış elemanlar bir adım sağa doğru boşluğu dolduracak şekilde ilerletilir. 7 sayısı boşalan yere geçer.
private static void insertionSort(int[] array)
{
//dizinin ilk elemanını yerinde bıraktık.
//2. elemanından başlıyoruz.
for (int i = 1; i <= (array.Length - 1); i++)
{
//araya sokacağımız veriyi tutuyoruz.
var current = array[i];
//hangi indexte bulunduğumuzu tutuyoruz.
int currentRealIndex = i;
//sola doğru yani sıralanmış kayıtlar arasında tarama yapıyoruz.
//Sayımızın büyük olduğu elemana kadar ilerleyip araya sokacağımız index değerini buluyoruz.
for (int j = i - 1; j >= 0 && currentRealIndex>0; j--)
{
if (array[j] < current)
break;
currentRealIndex--;
}
//araya sokulacak indexten sonraki tüm elemanları bir adım sağa kaydırıyoruz.
for (int j = i; j > currentRealIndex; j--)
{
array[j] = array[j - 1];
}
//araya elemanımızı yerleştiriyoruz.
array[currentRealIndex] = current;
}
}
Örnek uygulamaya aşağıdaki link ile erişebilirsiniz.
