Böl ve Fethet ile Garantili O(n log n)
Böl ve Fethet
Her zaman!
Sıra korunur
En iyi seçim
Merge Sort, John von Neumann tarafından 1945'te icat edildi ve "garantili performans" gerektiren durumlarda tercih edilir.
Quick Sort O(n²)'ye düşebilir. Merge Sort HER ZAMAN O(n log n). Real-time sistemlerde bu kritik!
Linked List'te random access yok. Quick Sort'un partition'ı kötü çalışır. Merge Sort O(1) ek alan ile çalışır!
Eşit elemanların sırası korunur. Python'ın sorted() ve Java'nın object sort'u Merge Sort kullanır!
Merge Sort, "Böl ve Fethet" (Divide and Conquer) stratejisini kullanan verimli bir sıralama algoritmasıdır. Diziyi sürekli ikiye böler, sonra sıralı şekilde birleştirir.
Diziyi ikiye böl
Alt dizileri recursive sırala
Sıralı alt dizileri birleştir
Örnek: [38, 27, 43, 3, 9, 82, 10]
İki sıralı diziyi tek sıralı dizide birleştirme:
Her iki diziden en küçüğü seç ve sonuca ekle → O(n)
| Durum | Zaman | Açıklama |
|---|---|---|
| En İyi | O(n log n) | Her zaman aynı |
| Ortalama | O(n log n) | Her zaman aynı |
| En Kötü | O(n log n) | Her zaman aynı - GARANTİLİ! |
| Alan | O(n) | Geçici dizi gerektirir (dezavantaj) |
def merge_sort(arr, depth=0):
"""
Merge Sort - Böl ve Fethet
"""
indent = " " * depth
print(f"{indent}merge_sort({arr})")
# Base case: 1 veya 0 elemanlı dizi zaten sıralı
if len(arr) <= 1:
return arr
# BÖL: Ortadan ikiye ayır
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
print(f"{indent} Sol: {left}, Sağ: {right}")
# FETHET: Recursive olarak sırala
left_sorted = merge_sort(left, depth + 1)
right_sorted = merge_sort(right, depth + 1)
# BİRLEŞTİR: İki sıralı diziyi birleştir
merged = merge(left_sorted, right_sorted)
print(f"{indent} Birleşti: {merged}")
return merged
def merge(left, right):
"""İki sıralı diziyi birleştirir"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Kalan elemanları ekle
result.extend(left[i:])
result.extend(right[j:])
return result
# Test
dizi = [38, 27, 43, 3, 9, 82, 10]
print(f"Başlangıç: {dizi}\n")
sonuc = merge_sort(dizi)
print(f"\n{'='*40}")
print(f"Sonuç: {sonuc}")Merge Sort iki farklı yaklaşımla implemente edilebilir:
Yaklaşım: Recursive. Büyük diziyi sürekli ikiye böl, sonra birleştir.
✅ Anlaması kolay (natural recursion)
✅ Early termination (sıralı alt dizi)
❌ O(log n) call stack kullanır
Yaklaşım: Iterative. Tek elemanlı parçalardan başla, giderek büyüt.
✅ Stack overflow riski yok
✅ Cache-friendly (sequential access)
❌ Kod biraz daha karmaşık
def merge_sort_bottom_up(arr):
"""
Bottom-Up Merge Sort - Iterative yaklaşım
Stack overflow riski yok!
"""
n = len(arr)
if n <= 1:
return arr
# Çalışma dizisi
result = arr.copy()
temp = [0] * n
# size: merge edilecek alt dizi boyutu
size = 1
while size < n:
print(f"Size {size}: {result}")
# Her (size*2) blok için merge yap
for left in range(0, n, 2 * size):
mid = min(left + size, n)
right = min(left + 2 * size, n)
# Merge işlemi
i, j, k = left, mid, left
while i < mid and j < right:
if result[i] <= result[j]:
temp[k] = result[i]
i += 1
else:
temp[k] = result[j]
j += 1
k += 1
while i < mid:
temp[k] = result[i]
i += 1
k += 1
while j < right:
temp[k] = result[j]
j += 1
k += 1
# Sonucu kopyala
result = temp.copy()
size *= 2
return result
# Test
dizi = [38, 27, 43, 3, 9, 82, 10]
print("Bottom-Up Merge Sort\n" + "="*30)
sonuc = merge_sort_bottom_up(dizi)
print(f"\nSonuç: {sonuc}")