Merge Sort (Birleştirmeli Sıralama)

Merge Sort (Birleştirmeli Sıralama), divide and conquere yaklaşımına sahip bir sıralama algoritmasıdır. Yani elimizdeki diziyi sonuna kadar parçalar ve sonrasında birleştiririz.

Bu algoritmanın adımlarını şu şekil ifade edebiliriz.
1-Sıralı olmayan listeyi ortadan eşit olarak iki alt listeye ayır .(Bu adım liste ikiye ayrılmayana dek devam eder.)
2-Alt listeleri kendi içinde sırala.
3-Sıralı iki alt listeyi tek bir sıralı liste olacak şekilde birleştir.

Bir sayı dizisi üstünde örneklendirecek olursak;
Dizimiz : 45-56-28-18-72-14-23-32

[45-56-28-18]  [72-14-23-32]                       //Dizimizi ikiye ayırdık
[45-56]  [28-18]  [72-14]  [23-32]                 //Tekrar ikiye ayırıyoruz.
[45] [56] [28] [18] [72] [14] [23] [32]            //Dizimiz parça parça oldu.
 \          /   \        /    \         /    \        /    
 [45-56]   [18-28]   [14-72]    [23-32]           //İkili ikili sıralı bir şekilde birleştirmeye başlıyoruz.
  \                      /        \                    /
  [18-28-45-56]        [14-23-32-72]              //Yeniden sıralı bir şekilde birleştirme yapıyoruz.
   \                                                 /
      [14-18-23-28-32-45-56-72]                   // Tüm diziyi sıralı bir şekilde birleştiriyoruz.


Bu algoritma recursive şekilde gerçeklenir.
Merge sort sıralama algoritmasının java kodu aşağıdaki şekilde olur.

public static void mergeSort(int array[],int lo, int n){
int bas = lo;
int son = n;
if (bas >= son) {
return;
}
int middle = (bas + son) / 2;
mergeSort(array, bas, middle);
mergeSort(array, middle + 1, son);
int basinSonu = middle;
int sonunBasi = middle + 1;
while ((bas <= basinSonu) && (sonunBasi <= son)) {
if (array[bas] < array[sonunBasi]) {
bas++;
} else {
int Temp = array[sonunBasi];
for (int k = sonunBasi- 1; k >= bas; k--) {
array[k+1] = array[k];
}
array[bas] = Temp;
bas++;
sonunBasi++;
}
}
}    

Kolay gelsin.