---
title: 'Birleştirmeli Sıralama'
source: 'https://academia.sh/tr/kurslar/algoritmalar/birlestirmeli-siralama'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:43+00:00'
license: 'CC BY-SA 4.0'
---

# Birleştirmeli Sıralama

Böl ve yönet ile kararlı sıralama, birleştirme işleminin doğruluğu, alttan yukarı değişke, dış sıralama ve ters çift sayımı.

Karesel algoritmalar milyonluk verilerde kullanılamaz. Karmaşıklık Hesaplama Yöntemi
dersinde çözülen bağıntı, çıkış yolunu zaten göstermişti:

$$
T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n)
$$

Bu ders, o bağıntıyı üreten algoritmayı kurar: diziyi ikiye böl, her yarıyı sırala,
sıralı iki yarıyı birleştir.

## Birleştirme

Algoritmanın çekirdeği, **sıralı iki diziyi tek sıralı diziye** birleştirmektir. İki
imleç kullanılır; her adımda küçük olan alınır.

```python
def birlestir(sol: list[int], sag: list[int]) -> list[int]:
    """Sıralı iki diziyi sıralı tek diziye birleştirir.

    Değişmez: sonuç, iki dizinin alınmış elemanlarının sıralı hâlidir
    ve alınmayan her eleman sonuçtaki her elemandan küçük değildir.
    """
    sonuc: list[int] = []
    i = j = 0
    while i < len(sol) and j < len(sag):
        if sol[i] <= sag[j]:            # eşitlikte sol öncelikli: kararlılık
            sonuc.append(sol[i])
            i += 1
        else:
            sonuc.append(sag[j])
            j += 1
    sonuc.extend(sol[i:])               # biri bittiğinde diğerinin kalanı eklenir
    sonuc.extend(sag[j:])
    return sonuc


print(birlestir([1, 5, 9], [2, 5, 6]))     # [1, 2, 5, 5, 6, 9]
```

Birleştirme $O(n)$'dir: her eleman tam bir kez alınır ve bir daha bakılmaz.

`<=` işareti kararlılığın kaynağıdır. Eşitlikte soldaki — yani girdide önce gelen — eleman
seçilir. `<` yazılırsa algoritma kararlılığını yitirir; bu, tek karakterlik bir farkın
davranışsal bir özelliği belirlediği örneklerden biridir.

## Böl ve Yönet

Kalan yalnızca özyinelemeli çatıdır.

```python
def birlestirmeli_siralama(dizi: list[int]) -> list[int]:
    if len(dizi) <= 1:                  # taban durumu: sıfır veya tek eleman sıralıdır
        return list(dizi)
    orta = len(dizi) // 2
    sol = birlestirmeli_siralama(dizi[:orta])
    sag = birlestirmeli_siralama(dizi[orta:])
    return birlestir(sol, sag)


print(birlestirmeli_siralama([5, 2, 9, 1, 5, 6]))      # [1, 2, 5, 5, 6, 9]
print(birlestirmeli_siralama([]))                      # []
print(birlestirmeli_siralama([3, 3, 3]))               # [3, 3, 3]
```

Doğruluğu tümevarımla gerekçelendirilir: taban durumu doğrudur; iki yarı doğru sıralanmışsa
birleştirme işlemi de doğru bir sıralı dizi üretir. Sonlanma, alt problemlerin kesin olarak
küçülmesinden gelir — `orta` hesabı, her iki parçanın da boş olmamasını sağlar.

## Maliyet

Özyineleme ağacının her düzeyinde toplam $n$ birim birleştirme işi yapılır ve düzey sayısı
$\log_2 n$'dir. Bölme, girdinin içeriğine bakmadan yapıldığı için **her durumda** aynıdır:

| Durum | Karşılaştırma | Sınıf |
|---|---|---|
| En iyi | $\sim \frac{n \log_2 n}{2}$ | $\Theta(n \log n)$ |
| Ortalama | $\sim n \log_2 n$ | $\Theta(n \log n)$ |
| En kötü | $\sim n \log_2 n$ | $\Theta(n \log n)$ |

Girdi ne olursa olsun aynı maliyet — bu güvence, sonraki dersteki hızlı sıralamanın
sahip olmadığı özelliktir.

Alan maliyeti algoritmanın zayıf noktasıdır: birleştirme, sonuç için $O(n)$ ek dizi
kullanır. Buna özyineleme yığıtının $O(\log n)$ derinliği eklenir. Dizi üzerinde çalışan
yerinde birleştirme değişkeleri vardır, ancak sabitleri büyüktür ve kodu karmaşıklaştırır.

```python
def sayimli_siralama(dizi: list[int]) -> tuple[list[int], int]:
    """(sıralı dizi, karşılaştırma sayısı)"""
    if len(dizi) <= 1:
        return list(dizi), 0
    orta = len(dizi) // 2
    sol, a = sayimli_siralama(dizi[:orta])
    sag, b = sayimli_siralama(dizi[orta:])
    sonuc: list[int] = []
    i = j = sayac = 0
    while i < len(sol) and j < len(sag):
        sayac += 1
        if sol[i] <= sag[j]:
            sonuc.append(sol[i]); i += 1
        else:
            sonuc.append(sag[j]); j += 1
    sonuc.extend(sol[i:]); sonuc.extend(sag[j:])
    return sonuc, a + b + sayac


import math
for n in (16, 1024, 65_536):
    veri = [(i * 7919) % n for i in range(n)]        # düzenli ama sıralı olmayan girdi
    print(n, sayimli_siralama(veri)[1], int(n * math.log2(n)))

# 16 35 64
# 1024 8929 10240
# 65536 956515 1048576
```

Ölçülen karşılaştırma sayısı $n \log_2 n$ tahmininin altında kalır; birleştirmede bir dizi
erkenden tükendiğinde kalan elemanlar karşılaştırmasız aktarıldığı için gerçek sayı
sınırın biraz altındadır. Mertebe aynıdır.

## Alttan Yukarı Değişke

Aynı algoritma özyinelemesiz yazılabilir: önce bir elemanlık bloklar ikişer ikişer
birleştirilir, sonra ikişerlikler, sonra dörderlikler.

```python
def alttan_birlestirmeli(dizi: list[int]) -> list[int]:
    d = list(dizi)
    genislik = 1
    while genislik < len(d):
        for bas in range(0, len(d), 2 * genislik):
            orta = min(bas + genislik, len(d))
            son = min(bas + 2 * genislik, len(d))
            d[bas:son] = birlestir(d[bas:orta], d[orta:son])
        genislik *= 2
    return d


print(alttan_birlestirmeli([5, 2, 9, 1, 5, 6]))        # [1, 2, 5, 5, 6, 9]
print(alttan_birlestirmeli([4, 3, 2, 1]))              # [1, 2, 3, 4]
```

Sonuç aynıdır, yığıt alanı harcanmaz. Uyarlanabilir bir değişke, bir elemanlık bloklar
yerine girdide zaten sıralı olan **koşuları (run)** başlangıç blokları sayar; neredeyse
sıralı veride düzey sayısını düşürür.

## Ardışık Erişimle Çalışması

Birleştirme, elemanlara baştan sona tek yönde erişir; rastgele erişim gerektirmez. Bu
özellik iki alanda belirleyicidir.

**Bağlı listelerde.** Veri Yapıları kursundaki bağlı listede orta elemana gitmek
doğrusaldır, ama birleştirme yalnızca bağlantı yeniden yönlendirmesiyle yapılır. Bağlı
listeler için pratikte tercih edilen sıralama budur ve ek dizi gerektirmez.

**Dış sıralamada.** Veri belleğe sığmıyorsa, parçalar tek tek belleğe alınıp sıralanır,
diske yazılır, sonra sıralı parçalar akış hâlinde birleştirilir. Birleştirmenin tek yönlü
okuma yapması, disk veya ağ üzerinden ardışık okumayı mümkün kılar — Bilgisayarlar Nasıl
Çalışır kursundaki yerellik ilkesinin doğrudan sonucu.

## Ters Çiftleri Saymak

Bir önceki dersteki ters çift sayısı, kaba kuvvetle $O(n^2)$'de hesaplanıyordu.
Birleştirme sırasında sağdaki elemanın öne geçtiği her durum, soldaki **kalan tüm
elemanlarla** ters çift oluşturur; bu gözlem sayımı $O(n \log n)$'e indirir.

```python
def ters_cift_hizli(dizi: list[int]) -> tuple[list[int], int]:
    if len(dizi) <= 1:
        return list(dizi), 0
    orta = len(dizi) // 2
    sol, a = ters_cift_hizli(dizi[:orta])
    sag, b = ters_cift_hizli(dizi[orta:])
    sonuc: list[int] = []
    i = j = sayac = 0
    while i < len(sol) and j < len(sag):
        if sol[i] <= sag[j]:
            sonuc.append(sol[i]); i += 1
        else:
            sonuc.append(sag[j]); j += 1
            sayac += len(sol) - i        # soldaki kalan elemanların hepsi ters çift
    sonuc.extend(sol[i:]); sonuc.extend(sag[j:])
    return sonuc, a + b + sayac


print(ters_cift_hizli([5, 2, 9, 1, 5, 6])[1])      # 6
print(ters_cift_hizli([5, 4, 3, 2, 1])[1])         # 10
print(ters_cift_hizli(list(range(1000)))[1])       # 0
```

Sonuçlar kaba kuvvet sayımıyla aynıdır. Bu, böl ve yönet fikrinin sıralamanın ötesinde de
kullanıldığının ilk örneğidir: birleştirme adımına yapılan küçük bir ekleme, bambaşka bir
büyüklüğü hesaplar.

## Özet

- Birleştirmeli sıralama diziyi ikiye böler, yarıları sıralar ve sıralı yarıları
  doğrusal maliyetle birleştirir.
- Birleştirmede eşitlikte soldaki elemanın seçilmesi kararlılığı sağlar.
- Maliyet her durumda $\Theta(n \log n)$'dir; bölme girdinin içeriğine bağlı değildir.
- Ek alan $O(n)$'dir; bu, algoritmanın başlıca bedelidir.
- Alttan yukarı değişke özyineleme yığıtını ortadan kaldırır; koşu tabanlı değişke
  uyarlanabilirlik kazandırır.
- Ardışık erişimle çalıştığı için bağlı listelerde ve dış sıralamada tercih edilir.

## Sonraki Adım

Birleştirmeli sıralama güvenli ama ek alan ister. Sonraki ders, aynı doğrusal-logaritmik
mertebeyi yerinde çalışarak elde eden hızlı sıralamayı ele alacak — karşılığında en kötü
durum güvencesini kaybederek. Pivot seçiminin bu kaybı nasıl olasılığa çevirdiği dersin
merkezinde olacak.