Merge Sort Algoritması, John von Neumann tarafından 1945 yılında yayınlanmıştır. Türkçeleştirildiğinde “Birleştirmeli Sıralama”  anlamı çıkmaktadır.

Eleman kümesini (array/dizi) en küçük duruma getirene kadar sürekli ikili parçalara ayırır. Küçük parçalara ayırdığı bu parçaları kendi aralarında sıralayarak bütünü elde eder ve sıralamayı yapmış olur. Kısaca bu işlem için recursive (yinelemeli) fonksiyon yazdığımızda bizim tüm sıkıntılarımızı halledecektir.

Durum performansı O(n) ile O(n²) arasındadır. En kötü durum performansı (worst case performance) O(n log n)‘dir. En iyi durum performansı O(n)‘dir. Ortalama durum performansı O(n log n) kabul edilir.

7 tam sayılı bir eleman kümesi içerisinde yinelemeli olarak birleştirme sıralama algoritmasının nasıl yapıldığını yukarıda vermiş olduğum şekilde görebilirsiniz. Eleman kümesini sürekli yarıya bölerek, ortaya çıkan en küçük parçaları kendi aralarında sıraladı, tüme varım yöntemi ile bu parçaları birleştirme işlemini yaptı.

Yukarıdaki animasyonda, rastgele üretilmiş sayıları temsil eden noktaların nasıl merge sort algoritması ile sıralandığını görüyoruz. Tanımlardan anlam çıkartmakta güçlük çeken arkadaşlarımızın bu animasyonları dikkatle incelemesini tavsiye ederim.

8 elemanlı bir dizinin hangi adımlarla parçalandığını, en fazla kaç parçaya ayrılabileceğini, parçalara ayrıldıktan sonra hangi prosedüre göre yeniden birleştirildiğini yukarıdaki animasyon ile görmüş olduk.  Şimdi isterseniz bir de uygulama üzerinde inceleyelim.

C# Console Uygulaması

int[] Sirala(int[] Dizi){
if (Dizi.Length < 2)
{
   return Dizi;
}

int Uzunluk = Dizi.Length / 2;
int KalanUzunluk = Dizi.Length - Uzunluk;
int deger1 = 0, deger2 = 0, deger3 = 0, sinir = 0;
int[] EkDizi = new int[Uzunluk];
int[] YedekDizi = new int[KalanUzunluk];

for (int i = 0; i < Uzunluk; i++)
{
    EkDizi[i] = Dizi[i];
}

for (int k = Uzunluk; k < Dizi.Length && sinir < KalanUzunluk; k++, sinir++)
{
    YedekDizi[sinir] = Dizi[k];
}

int[] siraliEkDizi = Sirala(EkDizi);
int[] siraliYedekDizi = Sirala(YedekDizi);

while (deger1 < Uzunluk && deger2 < KalanUzunluk)
{
   if (siraliEkDizi[deger1]  siraliYedekDizi[deger2])
   {
      Dizi[deger3] = siraliYedekDizi[deger2];
      deger2++;
      deger3++;
   }
}

while (deger1 < Uzunluk)
{
   Dizi[deger3] = siraliEkDizi[deger1];
   deger3++;
   deger1++;
}

while (deger2 < KalanUzunluk)
{
   Dizi[deger3] = siraliYedekDizi[deger2];
   deger3++;
   deger2++;
}

return Dizi;
}

Recursive (Yinelemeli) metod kullanacağımızı söylemiştik. O yüzden parametre olarak sıralaması yapılmamış dizimizi alan ve return olarak da diziyi sıralı bir şekilde veren fonksiyonumuzu tanımladık. Fonksiyonu tanımlamak yetmez bir de çağırmak lazım tabi.

static void Main(string[] args)
{
  int[] Dizi = new int[] { 6, 5, 3, 1, 8, 7, 2, 4 };
  Dizi = Sirala(Dizi);
}

Sıralama algoritmalarından Merge Sort Algoritmasını kavramaya çalıştık. Faydalı bir yazı olması dileğiyle. Sonraki yazı dizimizde görüşmek dileğiyle.