Merge sort adalah sort divide-and-conquer, stabil yang berjalan dalam waktu O(n log n) yang terjamin. Ia membagi array menjadi dua, mengurutkan setiap setengah secara rekursif, kemudian menggabungkan kedua setengah yang diurutkan.
Satu elemen sudah diurutkan (base case). Menggabungkan dua daftar yang diurutkan bersifat linear, dan kami melakukan log n level penggabungan.
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]
Ideal ketika Anda membutuhkan stabilitas atau O(n log n) yang terjamin, dan untuk linked list dan external sorting berkas yang sangat besar. Memori O(n) tambahan adalah kelemahan utamanya.
Merge sort menjamin O(n log n) terlepas dari input, tidak seperti kasus terburuk O(n²) quicksort.
Stabilitasnya menjaga urutan relatif kunci yang sama, yang penting untuk pengurutan multi-kunci.
Langkah penggabungan adalah primitif yang dapat digunakan kembali, dan struktur divide-and-conquer adalah template yang akan Anda gunakan kembali di mana-mana.