Merge Sort နှင့် Quick Sort — Divide-and-Conquer Sorting

နားလည်ထားရမယ့် အချက်

Merge sort နဲ့ quicksort နှစ်ခုစလုံးက divide-and-conquer သုံးပြီး simple sort တွေထက် ပိုမြန်စေတယ်၊ ဒါပေမယ့် work ကို ခွဲတဲ့နည်းက မတူဘူး — အဲဒီကွာခြားချက်ကပဲ trade-off အားလုံးရဲ့ အနှစ်ချုပ်ပါ။ Merge sort က array ကို middle ကနေ blindly ခွဲပြီး half နှစ်ခုကို recursive sort လုပ်ကာ၊ sorted half နှစ်ခုကို front element ငယ်တဲ့ဟာကို ထပ်ခါထပ်ခါ ယူပြီး merge လုပ်တယ် — ဒီ merge step ကပဲ equal element တွေရဲ့ original order ကို ထိန်းပေးလို့ merge sort က stable ဖြစ်တာပါ။ ၎င်းရဲ့ O(n log n) bound က unconditional ဖြစ်ပေမယ့် merge လုပ်ဖို့ array ဒုတိယတစ်ခု လိုအပ်တာမို့ O(n) extra memory ကုန်တယ်။ Quicksort ကတော့ pivot တစ်ခုရွေးပြီး array ကို ငယ်တဲ့ element ဘယ်ဘက်၊ ကြီးတဲ့ element ညာဘက် ကျအောင် partition လုပ်ကာ side နှစ်ဖက်ကို recurse ဆက်လုပ်တယ် — extra array မလိုအပ်လို့ in-place sort ဖြစ်တယ်။ Average case က O(n log n) ဖြစ်ပေမယ့် pivot ရွေးချယ်မှု consistently ညံ့ရင် (already-sorted input ပေါ်မှာ 'always pick the first element' လို naive pivot) partition တွေက lopsided ဖြစ်သွားပြီး O(n²) ကျဆင်းသွားနိုင်တယ်။ ဒါကြောင့် production quicksort implementation တွေက pivot ကို randomize လုပ်ရင်း median-of-three သုံးကြတာပါ — algorithm ရဲ့ real-world speed က ဒီ worst case ကို ရှောင်နိုင်မနိုင်အပေါ်မှာပဲ လုံးလုံးမှီတည်နေတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform က lesson batch တစ်ခုကြီးကို sort လုပ်တဲ့အခါ — ဥပမာ editorial update ပြီးနောက် topic တစ်ခုလုံးရဲ့ lesson list ကို re-rank လုပ်တဲ့အခါ — algorithm ရွေးချယ်မှုက အရေးကြီးလာတယ်။ Tie-breaking order (မူလ publish date အလိုက်) ကို sort ပြီးနောက်လည်း ထိန်းသိမ်းရမယ်ဆိုရင် merge sort ရဲ့ stability guarantee ကပဲ extra memory ကုန်လင့်ကစား safe default ဖြစ်တယ်။ ဒါပေမယ့် transient list သေးသေးလေးတစ်ခုကို one-off in-place sort လုပ်ချင်ရင် — view-count array ကို trending snapshot တွက်ဖို့ sort လုပ်တာလိုမျိုး — quicksort ရဲ့ in-place, extra-allocation မလိုတဲ့ behavior ကပိုကိုက်ညီတယ်၊ input က adversarially order မဖြစ်နေသရွေ့ပေါ့။ 'မြန်တဲ့ဟာ' ကိုသာ အမြဲရွေးမနေဘဲ situation က ဘယ် guarantee ကို တကယ်လိုချင်သလဲဆိုတာ ခွဲခြားနိုင်ဖို့ကပဲ ဒီနေရာက key skill ပါ။

• Merge sort က guaranteed O(n log n) ဖြစ်ပြီး stable ပါ၊ ဒါပေမယ့် O(n) extra memory လိုအပ်တယ်။
• Quicksort က average-case O(n log n) ဖြစ်ပြီး in-place ဖြစ်ပေမယ့် bad pivot ရွေးရင် worst-case O(n²) ကျနိုင်တယ်။
• Production quicksort တွေက pivot ကို randomize/median-of-three သုံးပြီး worst case ကို ရှောင်ကြတယ်။

အတူတူ စမ်းရေးကြည့်မယ်

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= keeps merge sort stable
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

[3, 9, 10, 27, 38, 43, 82] ဟု sorted list ကို print ထုတ်ပေးမည်။

Wikipedia — Merge sort — Data Structures & Algorithms