Sıralama Algoritmaları - 5. Birleştirmeli Sıralama (Merge Sort)

İngilizce Adı	Merge Sort
Ortalama	O(n log n)
En kötü	O(n log n)
Bellek	O(n)
Kararlı mı?	Evet
Yöntem	Karşılaştırma ile Birleştirme

Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.

Algoritmanın çalışması kavramsal olarak şöyledir:

1. Sıralı olmayan listeyi ortadan eşit olarak iki alt listeye ayırır.
2. Alt listeleri kendi içinde sıralar.
3. Sıralı iki alt listeyi tek bir sıralı liste olacak şekilde birleştirir.

Bu algoritma John von Neumann tarafından 1945 yılında bulunmuştur.

Kod örneği

public class BirlestirmeliSiralama
{
    int[] dizi;
    private int[] a, b; 

    public int[] Dizi
    {
        get { return dizi; }
        set { dizi = (int[])value.Clone(); }
    }
    public BirlestirmeliSiralama()
    {
    }

    public void Sirala()
    {
        a = Dizi;
        int n = a.Length;
        // according to variant either/or:
        b = new int[n]; 
        //b = new int[(n + 1) / 2];
        
        Sort(0, Dizi.Length - 1);
    }

    public override string ToString()
    {
        return "Birleştirmeli Sıralama";
    }

    void Sort(int lo, int hi)
    {
        if (lo < hi)
        {
            int m = (lo + hi) / 2;
            Sort(lo, m);
            Sort(m + 1, hi);
            Merge(lo, m, hi);
        }
    }

    void Merge(int lo, int m, int hi)
    {
        int i = lo, j = hi, k = lo;

        // copy first half of array a to auxiliary array b
        while (i <= m)
            b[k++] = a[i++];

        // copy second half of array a to auxiliary array b,
        // but in opposite order
        while (j > m)
            b[k++] = a[j--];

        i = lo; j = hi; k = lo;
        // copy back next-greatest element at each time
        // until i and j cross
        while (i <= j)
            if (b[i] <= b[j])
                a[k++] = b[i++];
            else
                a[k++] = b[j--];
    }
}

---

#sıralama-algoritmaları #sorthing-algorithms #birleştirmeli-sıralama #merge-sort