Merge sort hija ordni aqsam-u-ikkonkista, stabbli li taħdem fil-ħin O(n log n) garantit. Taqsam l-array in nofs, tordna kull nofs b'mod rikursiv, imbagħad tgħaqqad iż-żewg nofs li jkunu ordnati.
Element wieħed huwa diġà ordnat (każu bażi). Il-gaħdja ta' żewg listi ordnati hija lineari, u nsa b'log n livelli ta' gaħdja.
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]
Ideali meta għandek bżonn stabbiltà jew O(n log n) garantit, u għal listi konnessi u sortir estern ta' fajls kbar. Il-memorja O(n) addizzjonali hija d-difett prinċipali tagħha.
Merge sort tiggarantizza O(n log n) irrispettivament mill-input, b'differenza mill-każ agħar O(n²) ta' quicksort.
L-istabbiltà tagħha tippreserva l-ordni relattiva tal-ġwieki ugwali, li hija importanti għall-sortir multi-kjavi.
Il-pass tal-gaħdja hija primitiva li tista' titnieda, u l-istruttura aqsam-u-ikkonkista hija mudell li se titnieda darbtejn kullimkien.