Merge sort minangka algoritma urut divide-and-conquer, stabil sing lumampah ing wektu O(n log n) sing dijamin. Nggondhol array dadi loro, ngsort saben loro kanthi rekursif, banjur nggabung loro loro sing wis disort.
Siji elemen wis disort (basis case). Nggabung loro daftar sing wis disort minangka linear, lan kita nggawe log n tingkat nggabung.
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]
Ideyal nalika butuh stabilitas utawa O(n log n) dijamin, lan kanggo daftar berantai lan sortir eksternal file gede. Memori O(n) tambahan minangka kelemahan utama.
Merge sort njamin O(n log n) amargo input apa wae, ora kaya kasus paling awon O(n²) quicksort.
Stabilitase-e njaga urutan relatif kunci sing padha, sing penting kanggo sortir multi-kunci.
Langkah merge minangka primitif sing bisa digunakake maneh, lan struktur divide-and-conquer minangka template sing bakal digunakake maneh ngendi-mendi.