Merge sort — stable

Merge sort பாதியாகப் பிரித்து, மீண்டும் மீண்டும் வரிசைப்படுத்தி, இரண்டு sorted பாதிகளை O(n) இல் இணைக்கிறது. நிலைத்த stable, O(n log n) ஒப்பீட்டு வரிசை.

உண்மை உலகில் இது ஏன் முக்கியம்?

Python sorted/Timsort — merge இயல்பின் மீது hybrid. RAM விட பெரிய கோப்பு — வட்டில் sorted துண்டுகளை இணைத்தல். இணை தரவுத்தளம் பகிர்வுகளை இணைக்க merge pattern.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

T(n)=2T(n/2)+O(n) → O(n log n). இணைப்பில் இரண்டு சுட்டிகள்; அணி பதிப்பில் O(n) தற்காலிக அணி. சம நேரத்தில் இடது முன்னுரிமை — stable. கீழிருந்து merge — stack குறைப்பு.

Pythonில் முயற்சி செய்வோம்

def merge_sort(a: list[int]) -> list[int]:
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)


def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]


print(merge_sort([3, 1, 4, 1, 5, 9, 2, 6]))

அடிக்கடி நேரும் தவறுகள்

• slice நகல் — index வரம்பு பயன்படுத்தவும்.
• mid ஒற்றைப் பிழை.
• sentinel இல்லாமல் merge முடிவு சோதனை.

முக்கியச் சுருக்கக் குறிப்புகள்

• stable, கணிக்கத்தக்க O(n log n).
• கூடுதல் O(n) இடம் — quicksort உடன் வர்த்தகம்.
• merge → inversion, k-way.