Birleştirmeli Sıralama

#Nasıl çalışır?

Birleştirmeli sıralama (merge sort), "böl ve yönet" yaklaşımını kullanır: diziyi ikiye böler, her yarıyı ayrı ayrı sıralar, sonra iki sıralı yarıyı birleştirir.

Bölme işlemi, parçalar tek elemana inene kadar özyinelemeli olarak devam eder. Tek elemanlı bir dizi zaten sıralıdır.

Asıl iş birleştirme adımında yapılır: iki sıralı yarının en öndeki elemanları karşılaştırılır, küçük olan sonuca alınır. Bir yarı bitince diğerinin kalanı olduğu gibi eklenir.

#Canlı animasyon

mergeSort(a, lo, hi):
  if lo >= hi: return
  mid = (lo + hi) / 2
  mergeSort(a, lo, mid); mergeSort(a, mid + 1, hi)
  merge: repeatedly take the smaller front element
  append whatever is left

#Adım adım

1. 01Dizi tek elemanlıysa zaten sıralıdır; geri dön.
2. 02Diziyi ortadan ikiye böl.
3. 03Sol yarıyı merge sort ile sırala.
4. 04Sağ yarıyı merge sort ile sırala.
5. 05İki sıralı yarıyı birleştir: her adımda iki yarının önündeki elemanlardan küçük olanı al, sonra kalanları ekle.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def merge_sort(a: list[int]) -> list[int]:
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])

    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        # "<=" takes from the left on ties, which keeps the sort stable.
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


print(*merge_sort([5, 1, 4, 2, 8, 3]))

#Karmaşıklık

Dizi log₂ n kez ikiye bölünür ve her seviyede toplam n eleman birleştirilir: n · log n. Bu süre verinin sırasından bağımsızdır, en kötü durumda bile O(n log n) garanti edilir. Birleştirme için genellikle n boyutunda yardımcı bir dizi gerekir. (Animasyonda elemanları kaydırarak yerinde birleştiriyoruz ki hareketleri görebilesin.)

#Ne zaman kullanılır?

Garanti edilmiş O(n log n) süre ve kararlılık gerektiğinde idealdir. Bağlı listeleri sıralamak ve belleğe sığmayan büyük verileri dosyalar üzerinde sıralamak (external sort) için de standart yöntemdir. Python ve Java'nın nesne sıralaması merge sort tabanlı Timsort kullanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Etkinlik Seçimi
• Sayma Sıralaması (Counting Sort)
• Kruskal Algoritması
• Hızlı Sıralama