मर्ज सॉर्ट एक विभाजन-आणि-जय, स्थिर सॉर्ट आहे जो गॅरंटीड 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) मेमरी हा त्याचा मुख्य दोष आहे.
मर्ज सॉर्ट इनपुटचे परिस्थिती विचारात न घेता O(n log n) ची गॅरंटी देते, विपरीत quicksort च्या O(n²) सर्वात वाईट प्रकरणाच्या.
त्याची स्थिरता समान कुंजींचा सापेक्ष क्रम राखते, जो बहु-कुंजी सॉर्टिंगसाठी महत्वाचा आहे.
विलीन करण्याची पायरी पुन्हा वापरण्यायोग्य आदिम आहे, आणि विभाजन-आणि-जय संरचना एक टेम्पलेट आहे ज्याचा तुम्ही सर्वत्र पुन्हा उपयोग कराल.