Merge Sort’u Anlamak

Merge Sort muhtemelen en çok kafa karıştıran temel algoritmalardan birisidir. İnternette şöyle bir dolaşıp bakıldığında Merge Sort algoritmasının çok zor anlaşıldığını görüyorum. Hakikaten, temel algoritmalar açısından belli bir seviyeyi atlamak için Merge Sort ve benzeri algoritmaları anlayabilmek çok önemli.

MergeSort’un örnek kodlamasına bakalım:

MergeSort(Array, leftIndex, rightIndex){
  if (leftIndex >= rightIndex) return;//recursive gidişin durdurulması
  middleIndex = (rightIndex - leftIndex) / 2;  
  MergeSort(Array, leftIndex, middleIndex);//ilk mergeSort
  MergeSort(Array, middleIndex + 1, rightIndex);//ikinci mergeSort
  Merge(Array, leftIndex, middleIndex, rightIndex);
}

Örnek bir array’imiz olsun: Array = [1,5,3,6,4]

İlk defa MergeSort’un ana programda çağrıldığını düşünelim:

Array = [1,5,3,6,4];  
arrayLength = Array.length;//5
MergeSort(Array, 0, arrayLength - 1);//rightIndex değerimiz array'in uzunluğunun 1 eksiği olmalıdır çünkü array indexleri sıfırdan başlar.  

İlk MergeSort içerisinde middleIndex değerimiz 2 oluyor, yani (4–0)/2;
MergeSort içerisindeki ilk mergeSort çağrımı da: MergeSort(Array, 0, 2),
ikinci mergeSort çağrımı da MergeSort(Array, 3, 4) şeklinde oluyor. Görüldüğü gibi Array en başta orta noktadan 2ye ayrılıyor. Şimdilik recursive iç içe gidişleri görmezden gelelim. İlk mergeSort’un ele aldığı değerler hangileri? 0ıncı index ve 2inci indexler arasındaki değerler: 1,5,3. Recursive gidişatı görmezden gelerek direk ilk mergeSort’un 1,5,3 değerlerini sıraladığını düşünelim, sonuç: 1,3,5. İkinci mergeSort için de sonuç 4,6 olacak. İlk ve ikinci mergSort’ların işi bitince Merge işlemi yapıldığını biliyoruz. Aslında ilk ve ikinci mergeSort’ların recursive iç içe gidişlerinde de Merge yapılıyor ama dediğim gibi recursive akışı şimdilik görmezden gelelim ve Merge işlemine odaklanalım.

Merge işlemini hatırlayalım: Merge(Array, 0, 2, 4); // Array, leftIndex, middleIndex, rightIndex.

Array’in ilk kısmı ile ikinci kısmı kendi içinde sıralandı ve Array’imizin içi şu anda bu şekilde 1,3,5,4,6. Şimdi Merge metoduna parametre olarak Array’i, 0ıncı indexi, orta indexi-2, ve en sağ index değeri 4ü verelim. Bu ne anlama geliyor? İç içe recursive olarak çalışan işlemler sonucunda orta index değeri 2inci index’e kadar olan değerler sıralanmış vaziyette olduğunu ve 2inci index’ten sonraki değerlerin de kendi içinde sıralanmış olduğunu biliyoruz. Şimdi 2inci index’ten önceki ve sonraki kendi içinde sıralı olan değerler son kez karşılaştırılarak son kez sıralama ve birleştirme işlemi yapılacak Merge içerisinde.

Merge metodunu da yazalım:

Merge(Array, left, middle, right){
   n1 = middle - right + 1;
   n2 = right - middle;
//sol ve sağ sıralı array'lerin birbirleri ile kıyaslanabilmesi için sol ve sağ temp array'lerin oluşturulması gerekiyor.
   LeftTempArray = int[n1+1];//bir fazlası verilerek en son değer aşağıda MAX INT değeri olarak atanacak
   RightTempArray = int[n2+1];//bir fazlası verilerek en son değer aşağıda MAX INT değeri olarak atanacak
   //LeftTempArray'in doldurulması gerekiyor:
   for (int i = 0; i < n1; i++)
      LeftTempArray'in[i] = Array[left + i];
   LeftTempArray[n1] = Number.MAX_VALUE;
   //RightTempArray'in doldurulması gerekiyor:
   for (int i = 0; i < n2; i++)
      RightTempArray'in[i] = Array[middle + i +1];
   RightTempArray[n2] = Number.MAX_VALUE;
   leftCounter= 0, rightCounter = 0;
//sol ve sağ temp array'lerin değerleri kıyaslanıp ana array'de doğru sırada olması gereken değerler olması gereken index'lere işleniyor. Bu işlem kalem kağıt ile takip edilirse çok rahat anlaşılıyor.
   for (int i= left; i<= right; i++)
   {
        if (LeftTempArray[leftCounter] <= RightTempArray[rightCounter])
        {
            Array[i] = LeftTempArray[leftCounter];
            leftCounter++;
        }
        else
        {
            Array[i] = RightTempArray[rightCounter];
            rightCounter++;
        }
   }
}

Kodumuzu yazdığımıza göre basitçe Merge işlemini işleyelim.

Merge’e kadar Array’in son hali şu şekildeydi: 1,3,5,4,6. O zaman Merge’in parametrelerine bakalım. Merge([1,3,5,4,6], 0, 2, 4). Buna göre n1 değeri = 2–0+1=3. n2 değeri = 4–2 = 2; n1 ve n2 değerleri doğrultusunda sıralı olduğunu bildiğimiz kısımları elde etmemiz gerekiyor. Yani 1,3,5 ve 4,6 array’lerini oluşturacağız. Bunlar LeftTempArray ve RightTempArray olarak ifade edilecekler. LeftTempArray’in doldurulduğu loop’a bakarsak:

for (int i = 0; i < n1; i++)
  LeftTempArray'in[i] = Array[left + i];

left değeri zaten sıfır ve n1 değeri de 3 olduğuna göre LeftTempArray’in içerisine Array’in sıfırıncı, birinci ve ikinci index’indeki değerler sırasıyla doldurulacak, yani 1,3,5 değerleri dolacak. RightTempArray içerisine de ilgili loopu incelersek 4,6 değerleri dolacak. Ek olarak LeftTempArray ve RightTempArray’in en son index’lerine maximum integer değeri verilmişti. En sondaki for loop içerisinde LeftTempArray ve RightTempArray değeleri birbirleriyle kıyaslanıyor. Nasıl kıyaslandığını kalem kağıtla görmek çok kolay. Bu kıyaslama işlemi aslında sıralama işlemi ama bubbleSort gibi veya diğer n2 (n kare) süresinde sıralama yapan sort’lardan farklı bir sıralama işlemi yapıyor, çünkü zaten iki array kendi içerisinde sıralanmış olduğu bilindiği için bu array’lerin kendi içerisinde sıralaması yapılmıyor, doğrudan bu iki array kendi aralarında kıyaslanıyor yani n2 süresinde gerçekleşen bir işlem karmaşıklığından daha kısa sürede gerçekleşen n karmaşıklığında basit bir işlem yapılıyor. Recursive iç içe ikiye bölme yapıldığı için de logn karmaşıklığı geldiği için n*logn karmaşıklığındadır mergeSort algoritması ve bu nedenle bubbleSort gibi n2 karmaşıklığındaki sıralama algoritmalarından çok daha etkin bir algoritmadır.

Yukarıdaki açıklamalar doğrultusunda LeftIndex, RightIndex, MiddleIndex değerlerinin recursive olarak nasıl değiştiği, iç içe MergeSort’ların nasıl çalıştığı kalem kağıtla takip edilebilir. Kısaca, iç içe MergeSort’ları takip ettiğimizde hep ilk MergeSort’ların iç içe gittiğini ve ilk ulaşılan değerin, bizim örneğimizde 1 değerinin olduğunu ve ilk en içteki MergeSort çağrımı bitince en içteki ikinci MergeSort’a geçildiğini ve orada da 5 değerine ulaşıldığını ve sonrasın en içteki ilk Merge işleminin yapıldığını görebiliriz. Bu işlemlerden sonra diğer parçalama ve sıralama işlemlerine geçildiğini anlayabiliyoruz. İnternetteki birçok örnekte en alttaki değerlere sanki eş zamanlı ulaşılıyor gibi gösteriliyor ama öyle değil. MergeSort’un işleyişini en güzel anlatan videolardan birisi de sanırım şu linkteki olabilir: https://www.youtube.com/watch?v=7LN9z140U90