Merge sort एक divide-and-conquer, stable sort हो जो guaranteed O(n log n) समयमा चल्छ। यसले array लाई आधामा बिभाजन गर्छ, प्रत्येक आधालाई recursively sort गर्छ, त्यसपछि दुई sorted आधाहरूलाई merge गर्छ।
एकल element पहिले नै sorted छ (base case)। दुई sorted lists लाई merge गर्नु linear छ, र हामी log n स्तरको merging गर्छौं।
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]
आदर्श जब तपाईलाई stability वा guaranteed O(n log n) चाहिन्छ, र linked lists र external sorting को लागि विशाल फाइलहरू। अतिरिक्त O(n) मेमोरी यसको मुख्य drawback हो।
Merge sort ले O(n log n) guarantee गर्छ input को बाबजुद, quicksort को O(n²) worst case को विपरीत।
यसको stability ले equal keys को relative order लाई संरक्षण गर्छ, जो multi-key sorting को लागि महत्त्वपूर्ण छ।
Merge step एक reusable primitive हो, र divide-and-conquer structure एक template हो जो तपाई सर्वत्र पुनः प्रयोग गर्नुहुनेछ।