Merge Sort
- Türkçe karşılığı
- birleştirmeli sıralama
- Okunuşu
- mörc sort
Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.
Kısaca
Merge sort, bir listeyi ikiye bölen, her yarıyı özyinelemeyle sıralayan ve sıralı yarıları O(n log n) sürede birleştiren böl ve yönet sıralama algoritmasıdır.
Merge sort nedir?
Merge sort, bir listeyi her parça tek bir öğe içerene kadar, ki bu tanım gereği sıralıdır, tekrar tekrar ikiye bölen ve sonra bu parçaları sırayla yeniden birleştiren bir sıralama algoritmasıdır. 1945'te John von Neumann tarafından icat edilmiştir ve böl ve yönetin ders kitabı örneğidir. Çalışma süresi en iyi, ortalama ve en kötü durumda O(n log n)'dir; bu yüzden performansı şanssız girdide asla düşmez.
Asıl iş birleştirme adımında olur. Sıralı iki liste verildiğinde ilk öğelerini karşılaştırır, küçük olanı çıktıya taşır ve iki liste de boşalana kadar tekrarlarsınız; bu O(n) sürer. Liste yaklaşık log2(n) kez yarıya bölünür ve her bölme seviyesi toplamda n öğenin birleştirilmesini gerektirir; bu da genelde O(n log n) eder. Olağan dizi sürümü, birleştirilmiş çıktı için O(n) ek bellek gerektirir ve iki öğe eşit olduğunda sol yarıdan aldığı için merge sort kararlıdır (stable), yani eşit öğeleri özgün sırasında tutar.
Her biri öğrenci adına göre zaten sıralanmış iki sınav kâğıdı yığını düşünün: onları birleştirmek için alfabetik olarak önce gelen üstteki kâğıdı almaya devam edersiniz. Merge sort öngörülebilir performansın ya da kararlılığın önemli olduğu yerlerde kullanılır ve Python'ın sorted() fonksiyonunun ve Java'nın nesne sıralamasının arkasındaki melez algoritma olan Timsort'un temelidir. Birleştirme veriyi sıralı okuduğu için merge sort, belleğe sığmayan verinin diskte parçalar halinde sıralanıp parçaların sonra birleştirildiği harici sıralamaya (external sorting) da güç verir; veritabanları büyük ORDER BY sorgularını böyle ele alır. Birleştirme yalnızca düğümleri yeniden bağladığı ve ek bir dizi gerektirmediği için bağlı listelere de iyi uyar.
Merge sort en sık quicksort ile karşılaştırılır. Merge sort O(n log n) garanti eder ve kararlıdır, ancak diziler için O(n) ek bellek ister; quicksort yerinde sıralar ve CPU önbelleğini daha iyi kullandığı için pratikte genellikle daha hızlıdır, ancak O(n^2)'ye düşebilir ve kararlı değildir. Farkı hatırlamanın kullanışlı bir yolu: merge sort işini birleştirirken, quicksort bölerken yapar.
Önemli noktalar
- Merge sort bir listeyi ikiye böler, her yarıyı özyinelemeyle sıralar ve sonuçları birleştirir.
- En iyi, ortalama ve en kötü durumda O(n log n) sürede çalışır.
- Dizi sürümü O(n) ek bellek gerektirir.
- Kararlıdır: eşit öğeler özgün sırasını korur.
- Timsort'un ve belleğe sığmayan verinin harici sıralamasının temelindedir.
Örnek
def merge_sort(items):
if len(items) <= 1:
return items # base case: 0 or 1 items are already sorted
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:]) # divide
merged, i, j = [], 0, 0
while i < len(left) and j < len(right): # merge: O(n) per level
if left[i] <= right[j]: # <= keeps equal items in order (stable)
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:] # append whatever is left over
print(merge_sort([38, 27, 43, 3, 9, 82, 10])) # [3, 9, 10, 27, 38, 43, 82]Sık sorulan sorular
Merge sort'un zaman karmaşıklığı nedir?
Liste yaklaşık log n kez yarıya bölündüğü ve her seviye n öğeyi birleştirdiği için merge sort en iyi, ortalama ve en kötü durumda O(n log n) sürede çalışır. Dizileri sıralarken O(n) ek alan gerektirir.
Merge sort quicksort'tan daha mı iyidir?
Duruma bağlıdır. Merge sort O(n log n) garanti eder ve kararlıdır; bu da bağlı listelere, harici sıralamaya ve eşit öğelerin sırasını koruması gereken durumlara uygundur. Quicksort daha az bellekle yerinde sıralar ve diziler üzerinde pratikte genellikle daha hızlıdır.
Merge sort kararlı mıdır?
Evet, birleştirme adımı iki öğe eşit olduğunda sol yarıdan aldığı sürece. Kararlı bir sıralama gerektiğinde Timsort gibi birleştirme tabanlı algoritmaların kullanılmasının nedeni budur.
Sık karşılaştırılanlar
İlgili sayfalar
- Sıralama AlgoritmasıVeri Yapıları, s. 30Sıralama algoritması, öğeleri sayıları küçükten büyüğe ya da adları alfabetik olarak sıralamak gibi tanımlı bir düzene sokan adım adım bir yöntemdir.
- QuicksortVeri Yapıları, s. 28Quicksort, öğeleri seçilen bir pivot etrafında bölümleyen, sonra küçük ve büyük grupları aynı şekilde sıralayan bir böl ve yönet sıralama algoritmasıdır.
- Böl ve YönetVeri Yapıları, s. 6Böl ve yönet, bir problemi daha küçük bağımsız parçalara bölen, her birini özyinelemeyle çözen ve sonuçları birleştiren bir algoritma tasarım tekniğidir.
- ÖzyinelemeProgramlamanın Temelleri, s. 42Özyineleme, bir fonksiyonun sorunu, basit bir temel duruma ulaşana dek aynı sorunun daha küçük sürümleri için kendisini çağırarak çözdüğü tekniktir.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- Bağlı ListeVeri Yapıları, s. 4Bağlı liste, öğeleri ayrı düğümlerde saklayan bir veri yapısıdır; her düğüm bir değer ile zincirdeki sonraki düğüme bir referans tutar.
- Insertion SortVeri Yapıları, s. 20Insertion sort (eklemeli sıralama), sıralı listeyi öğe öğe kurar; her yeni öğeyi sıralanmışlar arasında yerine koyar, tıpkı eldeki kartları dizmek gibi.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin