Linked list merge sort

இணைப்புப் பட்டியலில் merge sort — O(n) கூடுதல் அணி இல்லாமல் next சுட்டிகளை மாற்றி O(n log n). நேர்காணலில் pointer + recursion பாலம்.

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

நினைவகக் கட்டுப்பாடு உள்ள worker-களில் இணைப்புப் பட்டியல் run-கள். குறைந்த தாமத ஒலி சங்கிலிகள் இணைப்பு இயல்பு; நகல் இல்லாமல் இணைப்பு cache நன்மை. போட்டியில் அணி மட்டுமே என்றாலும், இணைப்புப் பட்டியல் in-place merge சிந்தனையைக் கற்பிக்கிறது.

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

மெது/வேக சுட்டிகள் நடுவைக் கண்டுபிடித்து இரண்டாகப் பிரி. மீண்டும் மீண்டும் வரிசைப்படுத்து. dummy தலையுடன் இரண்டு sorted பட்டியல்களை இணை — ஒவ்வொரு படியிலும் சிறிய தலை. ஆழம் log n; மொத்தம் O(n log n). மிக நீளமான பட்டியலில் stack — bottom-up மேம்பட்டது.

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

# Conceptual sketch — Node class omitted; focus on merge pattern
def merge_two_sorted(h1, h2):
    dummy = cur = {"next": None}
    while h1 and h2:
        if h1["val"] <= h2["val"]:
            cur["next"], h1 = h1, h1["next"]
        else:
            cur["next"], h2 = h2, h2["next"]
        cur = cur["next"]
    cur["next"] = h1 or h2
    return dummy["next"]


print("merge_two_sorted is the heart of linked-list merge sort")

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

• splice இல் முனை இழப்பு — வரைபு முதல்.
• நீளம் இரட்டை/ஒற்றை — slow/fast முடிவு.
• பிரிப்பதற்கு முன் வாலைத் துண்டிக்க மறத்தல்.

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

• pointer merge — கூடுதல் அணி இல்லை; stack இல்லாமல் இல்லை.
• அணி merge sort போல் asymptotic.
• dummy node பயிற்சி.