Merge sort არის დელი-დაპყების, სტაბილური სორტირება, რომელიც გარანტირებული O(n log n) დროში მუშაობს. ის ყოფს მასივს შუაზე, რეკურსიულად სორტირებს თითოეულ ნახევარს, შემდეგ აერთიანებს ორ დასორტირებულ ნახევარს.
ერთი ელემენტი უკვე დასორტირებული არის (ბაზის შემთხვევა). ორი დასორტირებული სიის შერწყმა წრფივი და ჩვენ რობთ log n დონის შერწყმას.
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]
იდეალური, როდესაც გჭირდებათ სტაბილურობა ან გარანტირებული O(n log n), და დაკავშირებული სიებისა და უზარმაზარი ფайლების გარე სორტირებისთვის. დამატებითი O(n) მეხსიერება მისი მთავარი მინუსია.
Merge sort გარანტიას აძლევს O(n log n) დამოუკიდებელი შეყვანის, quicksort-ის O(n²) უარესი შემთხვევისგან განსხვავებით.
მისი სტაბილურობა ინარჩუნებს თანაბარი კლავიშების ფარდობით რიგს, რომელიც მნიშვნელოვანია მრავალკლავიშიანი სორტირებისთვის.
შერწყმის ნაბიჯი გამოყენებადი პრიმიტივია, ხოლო დელი-დაპყების სტრუქტურა ნიმუში, რომელიც ყველგან ხელახლა გამოიყენებთ.