Merge sort হল একটি divide-and-conquer, স্থিতিশীল সর্ট যা গ্যারান্টিযুক্ত 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²) সর্বোত্তম ক্ষেত্রের বিপরীতে।
এর স্থিতিশীলতা সমান কীগুলির আপেক্ষিক ক্রম সংরক্ষণ করে, যা বহু-কী সর্টিংয়ের জন্য গুরুত্বপূর্ণ।
মার্জ ধাপ পুনর্ব্যবহারযোগ্য primitive, এবং divide-and-conquer কাঠামো একটি টেমপ্লেট যা আপনি সর্বত্র পুনরায় ব্যবহার করবেন।