Birleştirmeli Sıralama Nedir?
İngilizce: Merge Sort
Yayın: · Son güncelleme:
Birleştirmeli Sıralama Nedir? Kısaca
Birleştirmeli sıralama (merge sort), listeyi tek elemanlı parçalara kadar ikiye bölen, sonra bu parçaları sıralı biçimde birleştirerek bütün listeyi sıralayan böl ve yönet algoritmasıdır. Her durumda O(n log n) sürede çalışır.
Birleştirmeli sıralama nedir?
Birleştirmeli sıralama, "iki sıralı listeyi birleştirmek kolaydır" fikrine dayanan bir sıralama algoritmasıdır. Liste önce defalarca ikiye bölünür. Her parça tek elemana inince, parçalar sıralı biçimde yeniden birleştirilir. 1945'te John von Neumann tarafından tanımlandığı kabul edilir.
Adım adım örnek
8, 3, 5, 1 listesini sıralayalım. Önce liste ikiye ayrılır: [8, 3] ve [5, 1]. Sonra her yarı tekrar bölünür: [8], [3], [5], [1]. Tek elemanlı listeler zaten sıralıdır.
Birleştirme aşamasında [8] ile [3] birleşip [3, 8] olur, [5] ile [1] birleşip [1, 5] olur. Son adımda iki listenin baş elemanları karşılaştırılır. 1, 3'ten küçük olduğu için önce o alınır. Ardından 3, sonra 5, en son 8 gelir. Sonuç 1, 3, 5, 8 olur.
Güçlü ve zayıf yönleri
Bu algoritmanın en büyük avantajı öngörülebilirliğidir. Liste ister rastgele ister ters sıralı olsun, süre her zaman O(n log n) olur. Ayrıca kararlıdır: aynı fiyattaki iki ürün, sıralamadan sonra da aynı göreli sırada kalır.
Zayıf yanı bellek kullanımıdır. Birleştirme sırasında geçici listeler gerektiği için, sıralanan veri kadar ek alan ister. Hızlı sıralama bu açıdan daha tasarrufludur.
Nerelerde kullanılır?
Belleğe sığmayan çok büyük dosyaların parça parça sıralanmasında birleştirmeli sıralama standart yöntemdir. Python'un sorted fonksiyonu ve Java'nın nesne listeleri için kullandığı Timsort, birleştirmeli sıralamayı eklemeli sıralamayla harmanlayan karma bir algoritmadır. Bağlı listeleri sıralamak için de en uygun seçeneklerden biridir.
Sıkça Sorulan Sorular
Birleştirmeli sıralama neden kararlıdır?
Birleştirme adımında eşit değerli iki elemandan soldaki önce alınır. Böylece eşit elemanların başlangıçtaki sırası korunur.
Merge sort mu quick sort mu tercih edilmeli?
Bellek sınırlıysa ve ortalama hız önemliyse hızlı sıralama öne çıkar. Kararlılık ve öngörülebilir süre gerekiyorsa ya da veri çok büyükse birleştirmeli sıralama daha uygundur.