Merge sort ni gawanya-na-taklifi, imara msomeko inayotumia O(n log n) wakati. Inaagiza eneo katikati, kurahisisha kila nusu kwa njia ya kujirudia, kisha kuchanganya nusu zote mbili zilizosomekwa.
Element moja yenyewe tayari inahitaji (kesi ya msingi). Kuchanganya orodha mbili zilizosomekwa ni mstari, na tunafanya viwango log n vya kuchanganya.
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]
Bora tunapohitaji imara au O(n log n) iliyohakikishwa, na kwa orodha zilizounganishwa na kurahisisha nje kwa faili kubwa. O(n) kumbukumbu ya ziada ni udhaifu wake mkuu.
Merge sort inahakikisha O(n log n) bila kujali ingizo, tofauti na O(n²) mbaya sana ya quicksort.
Imara yake inahifadhi mpango unaozingatiwa wa funguo sawa, ambalo linakubali kwa kurahisisha kwa ufunguo nyingi.
Hatua ya kuchanganya ni nzuri inayotumiwa tena, na muundo wa gawanya-na-taklifi ni kielelezo utakachotimizia tena kila mahali.