Birleştirmeli Sıralama - Merge Sort

  Merge sort (bireşen sıralama), diziyi ardışık olarak en küçük alt dizilerine kadar yarılayan sonra da onları sıraya koyarak bireştiren özyineli bir algoritmadır. Yarılama işlemi en büyük alt dizi en çok iki öğeli olana kadar sürer. Sonra merge (bireşim) işlemiyle altdiziler ikişer ikişer bölünüş sırasıyla sıralı olarak bir üst dizide bireşir. Süreç sonunda en üstte sıralı diziye ulaşılır.

Algoritmanın çalışma mantığı şu şekildedir. 
  Sıralı olmayan listeyi ortadan eşit olarak iki alt listeye ayırır.
  Alt listeleri kendi içinde sıralar.
  Sıralı iki alt listeyi tek bir sıralı liste olacak şekilde birleştirir.

Algoritmanın karmaşıklığı 
  Birleştirme sıralaması böl ve yönet algoritmasına güzel bir örnektir. Birleştirme sıralamasının karmaşıklığını hesaplamak için sıralanacak N elemanlı diziyi bir ağaç yapısına taşıyınca her bir düğüm bir alt diziyi temsil eder.
  Ağaç tam olarak n seviye içerir. k sayısı 0'dan n-1'e kadar ağaç seviyesini temsil etsin, yukarıdan aşağıya doğru ağacın k. seviyesinde 2^k tane düğüm bulunur. Bu düğümlerin her biri 2^{n-k}uzunluğunda bir alt diziyi temsil eder.
  Bir alt dizinin eleman sayısı 2^{n-k} olduğu için en fazla 2^{n-k} karşılaştırma yapılabilir. Ağacın her seviyesindeki alt dizi sayısı ve yapılabilecek en fazla karşılaştırma sayısı2^k . 2^{n-k} = 2^n ' dır. n seviye ağaç için toplam n . 2^n karşılaştırma yapılır. Elde edilen n . 2^n değerinin asimptotik üst sınırı O(NlgN) değeridir.

 Birleştirmeli sıralama algoritması java kodları

 public static void birlestirmeliSiralama(int alt, int üst,int[] sirasizDizi) {
  if (alt < üst) {
   int orta = (alt + üst) / 2;
   //sirasiz dizimi yerel değişken yaptığımdan diziyide metodlara yolladım
   birlestirmeliSiralama(alt, orta, sirasizDizi); 
   birlestirmeliSiralama(orta + 1, üst,sirasizDizi);
   birlestir(alt, orta, üst,sirasizDizi);
  }
 }

 public static void birlestir(int alt, int orta, int üst,int[] sirasizDizi) {
  int[] yedekDizi = new int[sirasizDizi.length];
  int i, j, k;
// a dizisinin her iki yarısını yedekDizi dizinine kopyala
  for (i = alt; i <= üst; i++) {
   yedekDizi[i] = sirasizDizi[i];
  }
  i = alt;
  j = orta + 1;
  k = alt;
  // her adımda bir sonraki en büyük terimi kopyala
  while (i <= orta && j <= üst) {
   if (yedekDizi[i] <= yedekDizi[j]) {
    sirasizDizi[k++] = yedekDizi[i++];
   } else {
    sirasizDizi[k++] = yedekDizi[j++];
   }
  }
// varsa, ilk yarıdan arta kalan terimlerin hepsini kopyala
  while (i <= orta) {
   sirasizDizi[k++] = yedekDizi[i++];
  }
 }

Kodlara ulaşmak için github adresine gidin