Merge Sort (Birleştirme) Sıralaması

Merge sort en verimli sıralama algoritmalarından biridir. Böl ve fethet stratejisine dayanır. Birleştirme sıralaması, bir listeyi her birinde yalnızca bir öğe olana kadar sürekli olarak birden çok alt listeye keser, ardından bu alt listeleri sıralanmış bir liste halinde birleştirir.

Böl ve fethet özyinelemeli olarak alt problemleri çözer; her alt problem orijinal problemden daha küçük olmalıdır ve her birinin bir temel durumu olmalıdır. Böl ve fethet algoritmasının üç bölümü vardır:

• Problemi aynı problemin çok sayıda küçük parçasına bölün.
• Alt problemleri özyinelemeli olarak çözerek ele geçirin. Yeterince küçüklerse alt problemleri temel durumlar olarak çözün.
• Orijinal problemin çözümlerini bulmak için alt problemlerin çözümlerini birleştirin.
• 

Çalışma Prensibi

• Dizinin ardışık iki alt dizisi birleştirilir.
• 
• Birleştirme için alt dizilerin kopyalarını oluşturulur.
• 
• Alt dizilerin ve ana dizinin geçerli indeksini korunur. Alt dizi ve ana dizinin kopyalarının indislerini tutulur.
• 
• L veya M'nin sonuna ulaşana kadar, L ve M öğeleri arasından daha büyüğünü seçilir ve A[p..r]'de doğru konuma yerleştirilir. Birinin sonuna ulaşana kadar sıralanmış alt dizilerin ayrı ayrı öğelerini karşılaştırılır.
• 
• L veya M'deki elemanlar bittiğinde, kalan elemanları toplanır ve A[p..r]'ye koyulur. İlk diziden kalan elemanları ana alt diziye kopyalanır.
• 
• İkinci dizinin kalan elemanlarını ana alt diziye kopyalanır.
• 

Java ile Merge Sort Algoritması

class MergeSort {
  void merge(int arr[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[] = new int[n1];
    int M[] = new int[n2];

    for (int i = 0; i < n1; i++)
      L[i] = arr[p + i];

    for (int j = 0; j < n2; j++)
      M[j] = arr[q + 1 + j];


    int i, j, k;
    i = 0;
    j = 0;
    k = p;


    while (i < n1 && j < n2) {
      if (L[i] <= M[j]) {
        arr[k] = L[i];
        i++;
      } else {
        arr[k] = M[j];
        j++;
      }
      k++;
    }
 

    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

    while (j < n2) {
      arr[k] = M[j];
      j++;
      k++;
    }
  }

  void mergeSort(int arr[], int l, int r) {
    if (l < r) {
      int m = (l + r) / 2;
      mergeSort(arr, l, m);
      mergeSort(arr, m + 1, r);

      merge(arr, l, m, r);
    }
  }


  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }


  public static void main(String args[]) {
    int arr[] = { 6, 5, 12, 10, 9, 1 };

    MergeSort ob = new MergeSort();
    ob.mergeSort(arr, 0, arr.length - 1);

    System.out.println("Sorted array:");
    printArray(arr);
  }
}