Is é Merge sort ná ordú divide-and-conquer, cobhsaí a fheidhmíonn in am ráthaithe O(n log n). Roinneanns sé an t-eagar in dhá leath, agus gach leath a shórtáil go hathchúrsach, ansin na dhá leath shórtáilte a fhúsiú.
Tá eilimint amháin i ndiaidh a bhheith i ndiaidh a bhheith críochnaithe cheana (cás bunúsach). Is líneach an fúsúnú dhá liosta shórtáilte, agus déanaimid log n leibhéal fúsúnaithe.
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]
Idéalach nuair a bhíonn gá agat do chobhsaithacht nó O(n log n) ráthaithe, agus do linked lists agus sórtú seachtrach comhad ollmhóra. Is é an fhaosmemory O(n) bhreise a phríomhdhíth.
Rathníonn merge sort O(n log n) beag beann ar an ionchur, murab ionann agus cás is measa O(n²) an quicksort.
Cobhsaíonn a thréithe ord a choibhneasaigh na heochracha comhionanna, rud a bhíonn tábhachtach do shórtú iolrach-eochrach.
Is primitive athúsáideach an chéim fúsúnaithe, agus tá an struchtúr divide-and-conquer ina themplate a bheidh tú ag athúsáid i ngach áit.