Mergesort
মার্জসর্ট
Array-কে অর্ধেক অর্ধেক ভেঙে দুই ভাগ sort করে একত্র merge করা divide-and-conquer — worst case-ও O(n log n), stable, কিন্তু O(n) extra memory লাগে।
also: merge sort, top-down mergesort
ভাঙা O(log n) স্তরে, প্রতি স্তরের merge O(n) — মোট O(n log n), input যেমনই হোক। Merge-এ মান সমান হলে বাম ভাগেরটা আগে নিলেই stability।
def merge(a, b):
out = []
while a and b:
out.append(a.pop(0) if a[0] <= b[0] else b.pop(0))
return out + a + bExtra memory-র খরচ আছে, কিন্তু access পুরো sequential — disk-এ বড় file sort (external sorting)-এ অপ্রতিদ্বন্ধী।
Python-এর sorted আর Java-র object sort — দুটোই Timsort,
mergesort-এর insertion-sort-hybrid বংশধর।