Merge sort ve dış sıralama

Merge sort veriyi ikiye böler, iki sıralı yarıyı iki pointer ile birleştirir. Birleştirme invariant'ı: sonuçta seçilmiş öğeler sıralıdır, kalan iki listenin başındaki en küçük öğe sonraki doğru seçimdir. Eşit anahtarda sol öğeyi önce alırsan stabiliteyi korursun.

Dengeli bölme sıralı/ters/tekrarlı girdilerde aynı Θ(n log n) zaman sınırını verir. Standart dizi uygulaması geçici tampon kullanır. Python slicing yarıları kopyalar; teorik indeks tabanlı uygulamayla allocation davranışı birebir aynı değildir. Linked list merge sort bağlantıları değiştirebilir fakat recursion alanı yine dikkate alınır.

Veri RAM'e sığmazsa external merge sort kullanılır: belleğe sığan run'ları sıralayıp diske yaz, sonra k-way merge yap. Öncelik kuyruğu her run'ın başını tutar; I/O, disk blokları ve buffer sayısı artık esas maliyet modelidir. Her şeyi RAM'e almak dış sıralama değildir.

Sıralama algoritması seçme atlası

Algoritma	Worst-case zaman	Tipik ek alan	Stable?
Insertion	Θ(n²)	O(1), in-place model	Evet, strict karşılaştırmayla
Merge	Θ(n log n)	O(n), standart array merge	Evet, eşitlikte soldan seç
Quick	Θ(n²)	Stack: worst O(n)	Standart swap sürümü hayır
Heap	Θ(n log n)	O(1), iteratif in-place	Hayır
Counting	Θ(n+k)	O(n+k), stable output	Uygun uygulamayla evet
Radix	Θ(d(n+k))	Digit yöntemine bağlı	Her pass stable olursa

Quick sort'un expected Θ(n log n) süresi worst-case Θ(n²)'yi silmez. Merge sort bağlı listede node relinking ile farklı ek alan takası sunabilir. Python örneğinde slice allocation vardır; teorik in-place iddiası bu koda otomatik aktarılmaz.

Merge invariantı: sonuç prefix'i sıralıdır ve tüketilmiş iki prefix'in bütün elemanlarını tam bir kez içerir. Bir sonraki küçük head'i seçmek bu invariantı korur. Eşit key'de soldan seçmek önceki sıra bilgisini korur. Sonunda kalan tek taraf zaten sıralı olduğundan eklenir.

Temel: [2,5,8] ile [1,5,7] merge'ünü trace et. Orta: (key, originalIndex) çiftleriyle stability testini yaz. İleri: RAM'e sığmayan 100 GB veri için run üretimi, fan-in, buffer boyutu ve disk pass sayısını tahmin et; RAM Big-O yerine I/O modelini kullan.

def merge_sort(a):
    if len(a) < 2: return list(a)
    m = len(a)//2
    left, right = merge_sort(a[:m]), merge_sort(a[m:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]: out.append(left[i]); i += 1
        else: out.append(right[j]); j += 1
    return out + left[i:] + right[j:]
assert merge_sort([5,1,4,2]) == [1,2,4,5]