Birleştirmeli Sıralama

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.

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.

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.

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.

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.

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.