# Merge Sort

Adres: https://softwaredictionary.org/tr/terimler/merge-sort
Kategori: Veri Yapıları
Son güncelleme: 2026-09-30
Türkçe karşılığı: birleştirmeli sıralama
Okunuşu: mörc sort

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: Python'da merge sort

```python
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.

---

Software Dictionary: https://softwaredictionary.org/tr · https://softwaredictionary.org/tr/llms.txt