Böl ve Fethet ile Garantili O(n log n)
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}")