Merge Sort (Birleştirme Sıralaması), 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 (Birleştirme)" 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ışması kavramsal olarak şöyledir:

1. Sıralı olmayan diziyi ortadan eşit olarak iki alt diziye ayırır.
2. Bu ayırma işlemi, alt diziler en çok iki elemanlı olana kadar devam eder.
3. Alt dizileri kendi içinde sıralar.
4. Sıralı iki alt diziyi tek bir sıralı dizi olacak şekilde birleştirir.
   
   

Merge Sort algoritması ile Heap Sort algoritması aynı zaman aralığına sahip olmalarına rağmen Heap Sort algoritması bellekte Merge Sort algoritmasına göre daha az yer tutar ve bu algoritmalar gerçeklendiğinde Heap Sort algoritması daha hızlı çalışır. Quick Sort algoritması da bellek tabanlı dizilerde Merge Sort'a göre daha hızlı çalışmaktadır. Ancak bağlı liste sıralamasında seçilebilecek en performanslı algoritma Merge Sort algoritmasıdır. Çünkü bağlı listelerin yapısı gereği mergesort bellekte fazladan sadece 1 birim yer tutar ve bağlı listelerin yavaş ve rastgele erişim performansı nedeniyle quicksort gibi diğer algoritmaların çalışma performansı düşer, Heap Sort gibi algoritmalar için ise imkansızdır.

Algoritmanın C# Programlama Diliyle Gerçeklenmesi

Aşağıdaki "Sırala" metodu ASP sayfasındaki "Sırala" düğmesine tıklandığı zaman çalıştırılacak kodları içermektedir. Bu metodda ilk olarak metin kutusuna girilen sayı kadar eleman alabilecek int türünden bir dizi tanımlanmıştır. Dizinin elemanları ise 1'den metin kutusuna girilen sayıya kadar olacak şekilde rastgele verilmiştir.

protected void Sırala(object sender, EventArgs e)
    {
        int n = Convert.ToInt32(tb.Text);
        int[] A = new int[n];      

        Random r = new Random();
        Stopwatch stopwatch = new Stopwatch();

        for (int i = 0; i < n; i++)
            A[i] = r.Next(1, int.Parse(tb.Text.Trim()));

        stopwatch.Start();
        MergeSort(A, 0, n - 1);
        stopwatch.Stop();

        TimeSpan timespan = stopwatch.Elapsed;
        string elapsedTime = String.Format("{0:00}.{1:000}",
        timespan.Seconds, timespan.Milliseconds);
        Response.Write("Gecen Zaman: " + elapsedTime);
    }

Aşağıdaki "Merge Sort" metodu tanımlanan diziyi, sadece iki elemanlı altkümeleri kalacak şekilde rekürsif olarak ayırır ve "Merge" metodu çağrılır.

    static void MergeSort(int[] A, int p, int r)
    {
        if (p < r)
        {
            int q = (p + r) / 2;
            MergeSort(A, p, q)
            MergeSort(A, q + 1, r);
            Merge(A, p, q, r);
        }
    }

Aşağıdaki "Merge" metodu sıralama işlemini gerçekleştiren metoddur. "MergeSort" metodu ile ayrılan dizi parçalarının elemanlarını, iki elemanlı en küçük dizilerden başlayarak sıralama işlemini gerçekleştirir. Daha sonra bir yanındaki iki elemanlı dizi ile birleştirerek sıralama işlemine devam eder ve sonunda tanımlanan dizi sıralanmış olur.

    static void Merge(int[] A, int p, int q, int r)
    {
        int n1 = q - p + 1;
        int n2 = r - q;
        int[] L = new int[n1 + 1];
        int[] R = new int[n2 + 1];

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

        for (int j = 0; j < n2; j++)
            R[j] = A[q + j + 1];

        L[n1] = Int32.MaxValue;
        R[n2] = Int32.MaxValue;

        int x = 0, y = 0;

        for (int k = p; k <= r; k++)
        {
            if (L[x] <= R[y])
            {
                A[k] = L[x];
                x++;
            }
            else
            {
                A[k] = R[y];
                y++;
            }
        }
    }

Bu uygulamanın çıktısı aşağıdaki gibi olacaktır.