Merge sort adalah pengurutan bagi-dan-taklukkan, stabil yang berjalan dalam waktu O(n log n) yang dijamin. Ia membagi larik menjadi dua, mengurutkan setiap setengah secara rekursif, kemudian menggabungkan dua setengah yang telah diurutkan.
Satu elemen sudah diurutkan (kasus dasar). Penggabungan dua daftar yang telah diurutkan bersifat linear, dan kami melakukan log n tingkat 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 memerlukan stabilitas atau O(n log n) yang dijamin, serta untuk daftar tertaut dan pengurutan eksternal file besar. Memori O(n) tambahan adalah kelemahan utamanya.
Merge sort menjamin O(n log n) terlepas dari masukan, tidak seperti kasus terburuk O(n²) quicksort.
Stabilitasnya mempertahankan urutan relatif kunci yang sama, yang penting untuk pengurutan multi-kunci.
Langkah penggabungan adalah primitif yang dapat digunakan kembali, dan struktur bagi-dan-taklukkan adalah templat yang akan Anda gunakan kembali di mana-mana.