Bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Merge Sort algoritması, 1945 yılında John von Neumann tarafından bulunmuştur.

Merge Sort, sıralanması istenen veri kümesini 2’ye bölme ve karşılaştırma işlemleri yaparak sıralamayı gerçekler.

6e60bf27ebc4da9041884fdf42d133a7[1] zamanda gerçeklenen algoritmanın algoritması aslında günlük hayatta çok sık başvurduğumuz bir yöndemdir:

  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.

 

merge sort

 

Örnek C++ kodu:

void mergesort (int *a, int l, int r)
{
    int m;
    if (l<r)
    {
        m = (l+r)/2;
        mergesort(a,l,m);    
        mergesort(a,m+1,r);
        merge (a,l,m,r);
    }
}

void merge (int *a, int l, int m, int r)
{
    int b[SIZE];
    int h,i,j,k;    
    
    i = l;
    j = m+1;
    k = l;

    while (i<=m && j<=r) 
    {
        if (a[i] <= a[j]) 
        {
            b[k] = a[i];
            i = i+1;
        }
        else if (a[i] > a[j]) 
        {
            b[k] = a[j];
            j = j+1;
        }
        k = k+1;
    }

    if (i>m) 
    {
        for (h=j; h<=r; h++)
            b[k+h-j] = a[h];
    }
    else if (j>r) 
    {
        for (h=i; h<=m; h++)
            b[k+h-i] = a[h];
    }

    for (h=l; h<=r; h++)
        a[h] = b[h];
}
Tags: , | Categories: Algoritma | C++