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