Birleştirmeli sıralama

Birleşmeli Sıralama (Merge Sort), bilgisayar bilimlerinde ${\displaystyle {\mathcal {O}}(n~\log(n))}$ derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır.

Birleştirmeli sıralama'nın rastgele üretilmiş sayıları gösteren noktaları nasıl sıraladığını gösteren örnek
Sınıf	Sıralama algoritması
Veri yapısı	Dizi
Zaman karmaşıklığı	O(n log n)
En iyi	Genellikle
Alan karmaşıklığı	En kötü durumda О(n)

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.

Algoritma

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. Sözde kod formatındaki bir algoritma örneği aşağıdaki gibidir.

function mergesort(m)
   var list left, right
   if length(m) ≤ 1
       return m
   else
       middle = length(m) / 2
       for each x in m up to middle
           add x to left
       for each x in m after middle
           add x to right
       left = mergesort(left)
       right = mergesort(right)
       result = merge(left, right)
       return result

Yukarıda kullanılan merge( ) fonksiyonunun değişik şekilleri olabilir. Bunlardan en basiti şöyledir.

function merge(left,right)
   var list result
   while length(left) > 0 and length(right) > 0
       if first(left) ≤ first(right)
           append first(left) to result
           left = rest(left)
       else
           append first(right) to result
           right = rest(right)
   if length(left) > 0 
       append left to result
   if length(right) > 0 
       append right to result
   return result

Karmaşıklık Hesabı

Birleştirme sıralaması böl ve yönet algoritmasına güzel bir örnektir. Algoritma her adımda diziyi ikiye bölüp en küçük birime geldiğinde bu alt dizileri sıralar ve daha sonra sıralanmış alt dizileri birleştirerek sonuca varır. 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 ${\textstyle 2^{k}}$ tane düğüm bulunur. Bu düğümlerin her biri ${\textstyle 2^{n-k}}$uzunluğunda bir alt diziyi temsil eder. Bir alt dizinin eleman sayısı ${\textstyle 2^{n-k}}$ olduğu için en fazla ${\textstyle 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ı ${\textstyle 2^{k}.2^{n-k}=2^{n}}$ ' dır.

n seviye ağaç için toplam ${\textstyle n.2^{n}}$ karşılaştırma yapılır. Elde edilen  ${\textstyle n.2^{n}}$ değerinin asimptotik üst sınırı ${\displaystyle O(NlgN)}$ değeridir.^[1]

Analiz

Birleştirme sıralaması örneğinde rastgele sayılardan oluşan bir liste sıralanıyor. Örnek olarak N adet elemanın sıralandığını düşünelim. Birleştirme sıralamasının ortalama durum ve en kötü durum olarak iki analizi vardır. Uzunluğu n olan bir liste üzerinde birleştirme sıralamasının işletim zamanı ${\textstyle T(N)}$ olsun. Bu sıralama bölünen alt listelere tekrarlı olarak uygulanırsa algoritmanın tanımından ${\textstyle T(N)=2T(N/2)+N}$ olur (Algoritmayı 2 alt listeye uygula ve birleşimden doğacak N basamağı ekle). Daha geniş bir analiz için master teoremine bakınız.

En kötü durum analizinde ${\textstyle (NlgN-2lgN+1)}$ olur. Bu da ${\textstyle (NlgN-N+1)}$ ile ${\textstyle (NlgN+N+O(lgN))}$ arasındadır. Bazı alt listelerin sıralanmış geldiğini düşünürsek ve n sayısı çok büyükken yapılan karşılaştırma sayısı en kötü durumdan x.n kez daha azdır. {x≈0,2645}

Birleştirme sıralaması en kötü durum performansında bile ortalama durumda çalışan bir hızlı sıralama algoritmasından %39 civarında daha az karşılaştırma yapar. İki algoritmanın eş zamanlı olarak çalıştığı durumda yani birleştirme sıralamasının en kötü durum performansı hızlı sıralamanın en iyi durumuna eşit olduğunda iki algoritmanın da karmaşıklığı Q(N logN) olarak eşittir. Birleştirme sıralamasının en iyi durumu en kötü durumun yarısı kadar karşılaştırma yapar.

Birleştirme sıralama fonksiyonu çağırıldığında, diziyi ikiye bölüp sadece iki diziyi sıraladığını düşünürsek oluşan her alt dizi için fonksiyonu tekrar tekrar çağırmamız gerekir. Bu da fonksiyonun 2N –l kez işlem görmesi demektir. Hızlı sıralama ise en kötü durumda bile N kez işlem görür. Bu durumda birleştirme sıralamasının hızlı sıralamaya oranla neredeyse iki kat bir maliyeti ortaya çıkar. Bundan sakınmak için fonksiyonun içine kendi kendini çağıran iteratif bir yapı koymak basit ve etkili bir çözümdür. Genellikle birleştirme sıralaması uygulamalarında verinin son hali girdi için ayrılan alana kaydedildiğinden bellekte ayrıca bir yer kaplamaz. Sıralama işlemini başka bir bellek alanında yapmak da mümkündür. Fakat bu oldukça karmaşıktır. Bu işlem performans olarak kazançlı olsa bile algoritma işletim zamanı hala Q(NlogN)'dir. Bu tip durumlarda algoritma yığın sıralama algoritması gibi çalışır. Sıralı erişim prensibine göre çalışan veri yapılarında birleştirme sıralaması hızlı sıralamaya oranla daha etkilidir.

Birleştirme sıralamasının optimizasyonu

Günümüz modern bilgisayarlarında konumsal yerellik ilkesi yazılım optimizasyonunda çok önemlidir. Bunun nedeni günümüzdeki çok katlı bellek sıradüzenselliğinin kullanımıdır.

Bir anlayışa göre ana RAM hızlı bir kaset sürücü gibi düşünülebilir. Ve daha hızlı olan ön bellekler. Ön belleğin tekrar tekrar yüklenmesi kabul edilemez zaman kayıplarını dayatmaktadır. Bu nedenle titiz bir birleştirme sıralaması işletim zamanında olumlu iyileştirmeler yapar. Fakat bu düşünce çok hızlı bellek elemanlarının ucuzlaması ve mimari de daha yaygın olarak kullanılmasıyla tersine de dönebilir.

Sonuç olarak bir birleştirme sıralaması tasarlamak, donanımsal değişiklikler gerektirir. Örneğin kaset sürücülerinin sayısında boyutunda veya hızında bazı değişiklikler yapılmalıdır.

Algoritmanın kodları

void Merge(int Alt, int Ust)
{
  if(Alt < Ust) return;
  int AltSinir= Alt;
  int UstSinir= Ust;
  int Pivot=(AltSinir+UstSinir)/2;
  Merge(AltSinir,Pivot);
  Merge(Pivot+1,UstSinir);
  int end_AltSinir=Pivot;
  int start_UstSinir=Pivot+1;
  while(( AltSinir<=end_AltSinir)&&(start_UstSinir<= UstSinir))
     {
      if(Dizi[AltSinir]<Dizi[start_UstSinir])
         AltSinir++;
      else
         {
           int T=AnaForm ->SIRALA[start_UstSinir];
           for( int k=start_UstSinir-1;k >= AltSinir; k--)
              Dizi[k+1]=Dizi[k];
           Dizi[AltSinir]=T;
           AltSinir++;
           end_AltSinir++;
           start_UstSinir++;
          }
     }
}  
           

1. Robert Sedgewick, Kevin Wayne, Algorithms 4th Edition, Addison-Wesley 2011 (chapter 2 p. 274)