Merge sort, garantili O(n log n) sürede çalışan böl-ve-fethet, kararlı bir sıralama algoritmasıdır. Diziyi ikiye böler, her yarıyı özyinelemeli olarak sıralar ve ardından iki sıralanmış yarıyı birleştirir.
Tek bir öğe zaten sıralanmıştır (temel durum). İki sıralanmış listeyi birleştirmek doğrusaldır ve log n düzey birleştirme yaparız.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Kararlılık veya garantili O(n log n) gerektiğinde ve bağlı listeler ile devasa dosyaların harici sıralaması için idealdir. Fazladan O(n) bellek ana dezavantajıdır.
Merge sort girdiye bakılmaksızın O(n log n) garantisi verirken, quicksort'un O(n²) en kötü durumu bunun aksine.
Kararlılığı, eşit anahtarların göreceli sırasını korur ki bu çok anahtarlı sıralama için önemlidir.
Birleştirme adımı yeniden kullanılabilir bir ilkel, ve böl-ve-fethet yapısı her yerde yeniden kullanacağınız bir şablondur.