Merge sort அடிப்படை

merge sort அடிப்படை — பிரிப்பு, அடிப்படை வழக்கு, நேரியல் இணைப்பு; in-place அல்லது galloping முன் இதை உறுதி செய்யவும்.

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

அறிமுக CS ஆய்வகம் merge — recursion மரம். வெள்ளைப் பலகை “merge எழுது” — index ஒழுங்கு. அடிப்படைக்குப் பிறகு கீழிருந்து மேல் merge sort.

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

ஒற்றை உறுப்பு வரை பிரி; அளவு 1+1 இணைப்பு எளிது. ஒவ்வொரு நிலையிலும் மொத்த வேலை O(n); நிலைகள் O(log n).

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

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


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

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

• slice நினைவக வெடிப்பு.
• அடிப்படை len<=1 மறத்தல்.
• merge வால் சேர்க்க மறத்தல்.

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

• recursion மரம் — காகிதம்.
• merge தனி பயிற்சி.
• Master theorem வழக்கு 2.