အခန်း ၁၁ - Sorting

Sorting (စီခြင်း) ဆိုတာ data တွေကို သတ်မှတ်ထားတဲ့ အစီအစဉ်တစ်ခု (ဥပမာ - အငယ်ဆုံးကနေ အကြီးဆုံး၊ A ကနေ Z) အတိုင်း ပြန်စီပေးတဲ့ လုပ်ငန်းစဉ် ဖြစ်ပါတယ်။ Developer တစ်ယောက်အနေနဲ့ data ကို စီရတာ နေ့စဉ်လိုလို ကြုံရပါတယ် — user တွေကို registration date အလိုက်၊ product တွေကို ဈေးနှုန်းအလိုက်၊ leaderboard ကို score အလိုက် စသဖြင့်ပါ။

ဒါပေမယ့် Sorting ဟာ "data စီတယ်" ဆိုတဲ့ အလုပ်တစ်ခုတည်းအတွက်ပဲ အရေးကြီးတာ မဟုတ်ပါဘူး။ စီပြီးသား (sorted) data ဟာ အလုပ်အများကြီးကို ပိုလွယ်စေပါတယ်။ ဥပမာ —

Binary Search (အခန်း ၉) လုပ်ဖို့ data က စီပြီးသား ဖြစ်ဖို့ လိုသည်။
ထပ်နေတဲ့ (duplicate) element တွေ ရှာဖို့ စီလိုက်ရင် ဘေးချင်းကပ် ရှာခြင်း။
အကြီးဆုံး/အငယ်ဆုံး k ခု ရှာဖို့ စီပြီး ထိပ်ကနေ ယူနိုင်သည်။
Interval, schedule ပြဿနာတွေဟာ စီပြီးမှ ဖြေရှင်းလို့ ရသည်။

ဒါကြောင့် Sorting ကို algorithm အများကြီးရဲ့ အခြေခံ စတင်အဆင့် (preprocessing step) အဖြစ် မြင်တတ်ဖို့ အရေးကြီးပါတယ်။

Sorting method တွေ အများကြီးရှိပါတယ်။ ဒါပေမယ့် အကုန်လုံးကို တန်းတူ အရေးထား လေ့လာစရာ မလိုပါဘူး။ ဒီအခန်းမှာ —

Basic Sorts (Bubble, Selection, Insertion) — concept နားလည်ဖို့အတွက်သာ။
Efficient Sorts (Merge, Quick, Heap) — real-world မှာ အသုံးတည့်တဲ့ $O(n \log n)$ sorts။
Non-comparison Sorts (Counting, Radix, Bucket) — special case တွေအတွက်။

ဆိုပြီး အပိုင်း ၃ ပိုင်း ခွဲ လေ့လာသွားပါမယ်။ လက်တွေ့မှာ programming language အများစုမှာ built-in sort function (Arrays.sort(), .sorted()) တွေ ပါပြီးသား ဖြစ်ပေမယ့်၊ နောက်ကွယ်က အလုပ်လုပ်ပုံ နားလည်ထားမှ ဘယ်အချိန် ဘာရွေးသုံးရမလဲ ဆုံးဖြတ်တတ်ပါမယ်။

Sorting ၏ အခြေခံ Concepts နှစ်ခု

Algorithm တွေ မလေ့လာခင်၊ sorting algorithm တိုင်းကို နှိုင်းယှဉ်တဲ့အခါ မေးရမယ့် မေးခွန်း ၂ ခု ရှိပါတယ် —

"Stable ဖြစ်လား?"
"In-place ဖြစ်လား?"

ဒီ concept ၂ ခုက algorithm ရွေးချယ်မှုကို တိုက်ရိုက် ဆုံးဖြတ်ပါတယ်။

Stable vs Unstable

Stable sort ဆိုတာ တန်ဖိုးတူတဲ့ element တွေရဲ့ မူလ အစီအစဉ် (relative order) ကို မပျက်စေဘဲ ထိန်းထားပေးတာ ဖြစ်ပါတယ်။

ဘာကြောင့် အရေးကြီးလဲ ဆိုတာ ဥပမာနဲ့ ကြည့်ရအောင်။ User list ကို အရင်က name အလိုက် စီထားပြီးသား ဖြစ်တယ် ဆိုပါစို့။ အခု age အလိုက် ထပ်စီချင်တယ်။

မူလ (name အလိုက် စီထားပြီး):
  Alice (25),  Bob (30),  Carol (25),  David (30)

age အလိုက် Stable sort လုပ်ရင်:
  Alice (25),  Carol (25),  Bob (30),  David (30)
  → age တူတဲ့ Alice, Carol တို့ဟာ မူလ name အစီအစဉ်အတိုင်း ကျန်သည်။

age အလိုက် Unstable sort လုပ်ရင်:
  Carol (25),  Alice (25),  David (30),  Bob (30)
  → age တူတဲ့ element တွေရဲ့ အစီအစဉ် ပျက်သွားနိုင်သည်။

Stable sort ဖြစ်မှ "age အလိုက် စီ၊ age တူရင် name အလိုက် စီ" ဆိုတဲ့ multi-field sorting ကို အဆင့်လိုက် (field တစ်ခုပြီးတစ်ခု) လုပ်လို့ ရပါတယ်။ ဒါကြောင့် real-world object sorting မှာ stability က အလွန် အရေးကြီးပါတယ်။

In-place vs Extra Memory

In-place sort ဆိုတာ memory အပို မယူဘဲ ( $O(1)$ extra space) မူလ array ထဲမှာတင် နေရာချင်းလဲပြီး စီတာ ဖြစ်ပါတယ်။ Extra memory လိုတဲ့ sort (ဥပမာ - Merge Sort) ကတော့ array အသစ်တွေ ဆောက်ပြီး စီတာ ဖြစ်လို့ data အရွယ်နဲ့ အချိုးကျ memory ပိုသုံးပါတယ်။

Data က သေးရင် ဒီ memory က ပြဿနာ မဟုတ်ပါ။ ဒါပေမယ့် memory အကန့်အသတ်ရှိတဲ့ စက် (embedded device) တွေ၊ ဒါမှမဟုတ် data အလွန်ကြီးတဲ့အခါ in-place ဖြစ်တာ အရေးကြီးလာပါတယ်။

အောက်က ဇယားက sorting algorithm အားလုံးရဲ့ ခြုံငုံ နှိုင်းယှဉ်ချက် ဖြစ်ပါတယ်။

Algorithm	Time (Average)	Time (Worst)	Space	Stable	အသုံးပြုရန်
Bubble Sort	$O(n^2)$	$O(n^2)$	$O(1)$	✅	လေ့လာရန် အတွက်သာ
Selection Sort	$O(n^2)$	$O(n^2)$	$O(1)$	❌	swap နည်းချင်ရင်
Insertion Sort	$O(n^2)$	$O(n^2)$	$O(1)$	✅	data သေး/စီပြီးသား
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n)$	✅	stable လိုရင်၊ linked list
Quick Sort	$O(n \log n)$	$O(n^2)$	$O(\log n)$ avg / $O(n)$ worst	❌	general-purpose (မြန်)
Heap Sort	$O(n \log n)$	$O(n \log n)$	$O(1)$	❌	memory အကန့်အသတ်ရှိရင်
Counting Sort	$O(n + k)$	$O(n + k)$	$O(n + k)$	✅*	integer, range သေး
Radix Sort	$O(d(n + k))$	$O(d(n + k))$	$O(n + k)$	✅	ကိန်းကြီး/string

Counting Sort က prefix sum နဲ့ output array သုံး ရေးမှသာ stable ဖြစ်ပါတယ်။
မှတ်ချက်: ဇယားထဲက "Stable" / "Space" တန်ဖိုးတွေဟာ ပုံမှန် (typical) implementation ကို ရည်ညွှန်းတာ ဖြစ်ပါတယ်။ ဥပမာ - Quick Sort ရဲ့ space က average $O(\log n)$ ဖြစ်ပေမယ့် pivot မကောင်းရင် worst case $O(n)$ ဖြစ်နိုင်ပါတယ်။

အပိုင်း ၁ — Basic Sorting Methods

ဒီ sort ၃ မျိုးက အကုန်လုံး $O(n^2)$ ဖြစ်ပြီး data ကြီးလာရင် နှေးပါတယ်။ ဥပမာ - element ၁ သန်း ( $n = 10^6$ ) ဆိုရင် $n^2 = 10^{12}$ ကြိမ် တွက်ရမှာ ဖြစ်လို့ နာရီနဲ့ချီ ကြာနိုင်ပါတယ်။ ဒါကြောင့် real-world မှာ အဓိက မသုံးပါဘူး။ ဒါပေမယ့် sorting ရဲ့ concept ("နှိုင်းယှဉ်ပြီး လဲ" ဆိုတဲ့ အခြေခံ) ကို နားလည်ဖို့ အကောင်းဆုံး စမှတ် ဖြစ်ပါတယ်။

Bubble Sort

Bubble Sort ဟာ ဘေးချင်းကပ် element ၂ ခုကို နှိုင်းယှဉ်ပြီး အစီအစဉ် မှားနေရင် လဲ (swap) လုပ်တဲ့ နည်းလမ်း ဖြစ်ပါတယ်။ Loop တစ်ပတ်ပြီးတိုင်း အကြီးဆုံး element က ရေပေါ်က ပူဖောင်း (bubble) လို နောက်ဆုံးနေရာကို တက်သွားတဲ့အတွက် ဒီနာမည် ရတာ ဖြစ်ပါတယ်။

[5, 1, 4, 2] ကို စီတဲ့ အဆင့်ဆင့်ကို အသေးစိတ် ကြည့်ရအောင်။ Pass ၁ (ဘေးချင်းကပ် နှိုင်းယှဉ်ခြင်း) —

နှိုင်းယှဉ်	array အခြေအနေ	လုပ်ဆောင်ချက်
`5` vs `1`	`[5, 1, 4, 2]`	`5 > 1` → လဲ → `[1, 5, 4, 2]`
`5` vs `4`	`[1, 5, 4, 2]`	`5 > 4` → လဲ → `[1, 4, 5, 2]`
`5` vs `2`	`[1, 4, 5, 2]`	`5 > 2` → လဲ → `[1, 4, 2, 5]`

Pass ၁ ပြီးတော့ အကြီးဆုံး 5 က နောက်ဆုံးနေရာ ရောက်သွားပါတယ်။ Pass ၂ မှာ [1, 4, 2] ကို ဆက်လုပ်ပြီး 4 က နေရာရ၊ Pass ၃ မှာ [1, 2] ကို လုပ်ပြီး စီပြီးသား ဖြစ်သွားပါတယ်။

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        // တစ်ပတ်တိုင်း အကြီးဆုံးက အနောက်ဆုံးရောက်လို့ (n-1-i) အထိသာ ကြည့်ရန် လုံလောက်
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // တစ်ပတ်လုံး swap မဖြစ်ရင် စီပြီးသား ဖြစ်လို့ ရပ်သည် (optimization)
        if (!swapped) break;
    }
}

swapped flag က optimization တစ်ခု ဖြစ်ပါတယ်။ Data က စီပြီးသား ဖြစ်နေရင် ပထမ pass မှာ ဘယ်တုန်းမှ swap မဖြစ်လို့ ချက်ချင်း ရပ်ပြီး $O(n)$ ဖြစ်သွားပါတယ်။

မှတ်ချက်: Bubble Sort ကို သင်ယူဖို့သက်သက် အတွက်သာ ဖြစ်ပြီး production code မှာ မသုံးသင့်ပါ။ ရိုးရှင်းပြီး နားလည်လွယ်ပေမယ့်၊ swap အကြိမ်ရေ အလွန်များတဲ့အတွက် basic sort ၃ ခုထဲမှာတောင် အနှေးဆုံး ဖြစ်ပါတယ်။ ကျောင်းသုံးစာအုပ်တွေမှာ နာမည်ကြီးပေမယ့်၊ လက်တွေ့မှာ Bubble Sort ကို interview နဲ့ classroom အပြင် ရှားရှားပါးပါး တွေ့ရတာက — တူညီအောင် ရိုးရှင်းတဲ့ Insertion Sort က ပိုကောင်းတဲ့ performance ပေးနိုင်လို့ ဖြစ်ပါတယ်။

Selection Sort

Selection Sort ဟာ စီမထားသေးတဲ့ အပိုင်းထဲက အငယ်ဆုံး element ကို ရွေး (select) ပြီး၊ စီပြီးသား အပိုင်းရဲ့ နောက်ဆုံးနေရာနဲ့ လဲတဲ့ နည်းလမ်း ဖြစ်ပါတယ်။ "အငယ်ဆုံးကို ရွေး၊ ရှေ့ထား" ဆိုတဲ့ အလုပ်ကို ထပ်ခါ လုပ်သွားတာ ဖြစ်ပါတယ်။

[5, 2, 4, 1] ကို စီကြည့်ရအောင် —

အဆင့်	စီမထားသေးသော အပိုင်း	အငယ်ဆုံး	လဲပြီးနောက်
၁	`[5, 2, 4, 1]`	`1`	`[1, 2, 4, 5]` (`5` နဲ့ `1` လဲ)
၂	`[2, 4, 5]`	`2`	`[1, 2, 4, 5]` (နေရာမှန်ပြီး)
၃	`[4, 5]`	`4`	`[1, 2, 4, 5]` (နေရာမှန်ပြီး)

void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        // i နောက်ပိုင်းမှ အငယ်ဆုံးကို ရှာသည်
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // အငယ်ဆုံးကို လက်ရှိနေရာ (i) နဲ့ လဲသည်
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Selection Sort ရဲ့ ထူးခြားချက်က swap (write) အကြိမ်ရေ နည်းတာ (အများဆုံး $n$ ကြိမ်) ဖြစ်ပါတယ်။ memory ထဲ ရေး (write) တာ ဈေးကြီးတဲ့ environment တွေ (ဥပမာ - flash memory၊ write count ကန့်သတ်ထားတဲ့ storage) မှာ Bubble Sort ထက် swap နည်းတဲ့အတွက် အသုံးဝင်နိုင်ပါတယ်။ (Java လို language မှာ object ကြီးတွေ swap လုပ်တာဟာ object တစ်ခုလုံး မဟုတ်ဘဲ reference ကိုသာ လဲတာ ဖြစ်လို့ "object ကြီးလို့ swap ဈေးကြီး" ဆိုတာ မမှန်ပါ။) ဒါပေမယ့် comparison ကတော့ data စီပြီးသား ဖြစ်နေရင်တောင် အမြဲ $O(n^2)$ ဖြစ်နေပါတယ်။ ဒါ့အပြင် Selection Sort က unstable ဖြစ်ပါတယ် — ဝေးတဲ့ element တွေကို လဲတဲ့အတွက် တန်ဖိုးတူ element တွေရဲ့ အစီအစဉ် ပျက်နိုင်ပါတယ်။

Insertion Sort

Insertion Sort ဟာ ဖဲချပ်တွေကို လက်ထဲမှာ စီတဲ့ ပုံစံ ဖြစ်ပါတယ်။ ဖဲတစ်ချပ် ထပ်ယူတိုင်း၊ လက်ထဲက စီပြီးသား ဖဲတွေကြားမှာ မှန်ကန်တဲ့နေရာကို ထိုးထည့်တာ မျိုးပါ။ Element တစ်ခုစီကို ယူပြီး၊ သူ့ရှေ့က စီပြီးသား အပိုင်းထဲမှာ မှန်ကန်တဲ့နေရာကို ထိုးထည့် (insert) ပါတယ်။

[5, 2, 4, 1] ကို စီကြည့်ရအောင်။ | က "ဒီ ဘယ်ဘက်ပိုင်းသည် စီပြီး" ဆိုတာ ပြပါတယ် —

ယူသော element	ဖြစ်စဉ်	array အခြေအနေ
(စတင်)	ပထမ element ကို စီပြီးသား ယူဆ	`[5 \| 2, 4, 1]`
`2`	`2 < 5` → `5` ကို ညာတွန်း၊ `2` ကို ရှေ့ထား	`[2, 5 \| 4, 1]`
`4`	`4 < 5` → `5` တွန်း၊ `4 > 2` → `4` ကို `2`,`5` ကြား	`[2, 4, 5 \| 1]`
`1`	`1` က အကုန်ထက်ငယ် → အရှေ့ဆုံး ထိုးထည့်	`[1, 2, 4, 5 \|]`

void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // ထိုးထည့်မယ့် element
        int j = i - 1;
        // key ထက် ကြီးတဲ့ element တွေကို တစ်နေရာစီ ညာဘက်တွန်းသည်
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // ဖြစ်ပေါ်လာတဲ့ နေရာလွတ်မှာ key ထည့်သည်
    }
}

အသုံးဝင်မှု: Insertion Sort ဟာ basic sort ၃ ခုထဲမှာ လက်တွေ့ အသုံးဝင်ဆုံး ဖြစ်ပါတယ်။

Small Data ဖြစ်ရင် $O(n^2)$ ဖြစ်ပေမယ့် overhead နည်းလို့ Quick/Merge Sort ထက်တောင် ပိုမြန်နိုင်သည်။

Nearly sorted ဖြစ်ရင် inner while loop က ဘာမှ မလုပ်ရဘဲ ကျော်သွားလို့ $O(n)$ နီးပါး ဖြစ်သည်။

ဒါကြောင့် Java, Python စတဲ့ language အများစုရဲ့ built-in sort ဟာ data အပိုင်းသေးတွေ ရောက်တဲ့အခါ Insertion Sort ကို အလိုအလျောက် တွဲသုံးကြပါတယ်။

အပိုင်း ၂ — Efficient Comparison Sorting

Basic sort တွေက ဘာကြောင့် နှေးသလဲ ဆိုရင်၊ element တစ်ခုကို သူနဲ့ ဝေးတဲ့ နေရာ ရောက်ဖို့ တစ်ဆင့်ချင်းသာ ရွှေ့လို့ ဖြစ်ပါတယ်။ Efficient sort တွေက Divide and Conquer (ခွဲပြီး အနိုင်ယူ) သဘောတရားနဲ့ ပြဿနာကို တစ်ဝက်စီ ခွဲဖြေတဲ့အတွက် $O(n \log n)$ ရအောင် လုပ်နိုင်ပါတယ်။

$O(n \log n)$ ဆိုတာ ဘာကြောင့် ကောင်းသလဲ? Element ၁ သန်းအတွက် $n^2 = 10^{12}$ ဖြစ်ပေမယ့် $n \log n \approx 2 \times 10^7$ သာ ဖြစ်ပါတယ်။ ၅ သိန်းဆ ပိုမြန်တာ ဖြစ်ပါတယ်။

Divide and Conquer ဆိုတာ ဘာလဲ

Merge Sort နဲ့ Quick Sort မလေ့လာခင်၊ သူတို့ ၂ ခုလုံးရဲ့ နောက်ကွယ်က Divide and Conquer (ခွဲပြီး အနိုင်ယူ) သဘောတရားကို အရင် နားလည်ထားရင် ပိုရှင်းပါတယ်။ ဒါက sorting တင် မဟုတ်ဘဲ algorithm design ရဲ့ အရေးကြီးဆုံး pattern တစ်ခု ဖြစ်ပါတယ်။

အယူအဆက ရိုးရှင်းပါတယ် — ပြဿနာကြီးတစ်ခုကို တိုက်ရိုက် မဖြေဘဲ၊ ပိုသေးတဲ့ ပြဿနာ ၂ ခု (သို့) အများ အဖြစ် ခွဲ၊ တစ်ခုစီ သီးသန့်ဖြေ၊ ပြီးမှ ပြန်ပေါင်း လုပ်တာ ဖြစ်ပါတယ်။ အဆင့် ၃ ဆင့် ရှိပါတယ် —

အဆင့်	အလုပ်	Merge Sort ဥပမာ
၁. Divide	ပြဿနာကို ပိုသေးတဲ့ subproblem အဖြစ် ခွဲသည်	array ကို တစ်ဝက်စီ ခွဲသည်
၂. Conquer	subproblem တစ်ခုစီကို (များသောအားဖြင့် recursion ဖြင့်) ဖြေသည်	တစ်ခုစီကို သီးသန့် စီသည်
၃. Combine	subproblem ၏ အဖြေများကို ပြန်ပေါင်းပြီး အဖြေအပြည့် ရယူသည်	စီပြီးသား ၂ ခြမ်းကို merge လုပ်သည်

ဒီ pattern ဟာ Recursion (အခန်း ၁၀) နဲ့ တိုက်ရိုက် ဆက်စပ်ပါတယ် — "ပြဿနာကြီးကို တူညီတဲ့ ပိုသေးတဲ့ ပြဿနာ အဖြစ် ခွဲ" ဆိုတဲ့ idea အတိုင်းပါပဲ။ ကွာတာက — recursion သက်သက်မှာ subproblem တစ်ခု ဆီ ဆင်းတတ်ပြီး၊ divide and conquer မှာ subproblem အများ (ပုံမှန် ၂ ခု) ဆီ ခွဲဆင်းပြီး အဖြေတွေ ပြန်ပေါင်းတာ ဖြစ်ပါတယ်။

ဘာကြောင့် မြန်သလဲ? ပြဿနာကို တစ်ဝက်စီ ခွဲတဲ့အတွက် အလွှာ (level) အရေအတွက်က $\log n$ ပဲ ရှိပါတယ်။ အလွှာတစ်ခုစီမှာ စုစုပေါင်း အလုပ်က $O(n)$ ဆိုရင် စုစုပေါင်း $O(n \log n)$ ဖြစ်ပါတယ်။ ဒါက basic sort တွေရဲ့ $O(n^2)$ ထက် များစွာ မြန်တဲ့ အကြောင်းရင်း ဖြစ်ပါတယ်။

ပြဿနာ (size n)
   ├── ခွဲ → subproblem (size n/2)
   │         ├── ခွဲ → subproblem (size n/4) ...
   │         └── ခွဲ → subproblem (size n/4) ...
   └── ခွဲ → subproblem (size n/2) ...
   
   အလွှာ log n ခု × အလွှာတစ်ခုစီ O(n) = O(n log n)

ဘယ်နေရာတွေမှာ တွေ့ရသလဲ? ဒီစာအုပ်မှာ divide and conquer ကို တွေ့ဖူးပြီးသား နေရာတွေ ရှိပါတယ် —

Binary Search (အခန်း ၉) — search space ကို တစ်ဝက်စီ ခွဲ (subproblem ၁ ခုကိုသာ ဆက်ဖြေ)။

Merge Sort / Quick Sort (ဒီအခန်း) — array ကို ခွဲ၊ စီ၊ ပြန်ပေါင်း။

ဒါကြောင့် divide and conquer ကို သီးခြား chapter အဖြစ် မလေ့လာဘဲ၊ သူ့ကို သုံးတဲ့ algorithm တွေကို လေ့လာခြင်းဖြင့် နားလည်သွားမှာ ဖြစ်ပါတယ်။

အခု Merge Sort နဲ့ Quick Sort တို့ဟာ ဒီ ၃ အဆင့်ကို ဘယ်လို အသုံးချလဲ ကြည့်ရအောင်။

Merge Sort

Merge Sort ဟာ idea ၂ ဆင့်နဲ့ အလုပ်လုပ်ပါတယ် —

Divide: array ကို element တစ်ခုစီ ဖြစ်သွားအောင် တစ်ဝက်စီ ဆက်တိုက် ခွဲသည်။
Merge: ခွဲထားတဲ့ ပိုင်းသေးတွေကို စီရင်း ပြန်ပေါင်း ဖို့လိုပါတယ်။ အပိုင်း ၂ ခုစလုံး စီပြီးသား ဖြစ်နေတဲ့အတွက် ပေါင်းတာ မြန်တယ်။

            [5, 2, 4, 1]
           /            \
       [5, 2]          [4, 1]
       /   \           /    \
     [5]   [2]       [4]    [1]      ← Divide (element ၁ ခုစီ ဖြစ်အောင်)
       \   /           \    /
       [2, 5]          [1, 4]
           \            /
            [1, 2, 4, 5]              ← Merge (စီရင်း ပြန်ပေါင်း)

Merge လုပ်ပုံ အသေးစိတ်: ဘာကြောင့် မြန်သလဲ ဆိုတာ နားလည်ဖို့ [2, 5] နဲ့ [1, 4] ကို ပေါင်းတာ ကြည့်ရအောင်။ ၂ ခုလုံးက စီပြီးသား ဖြစ်လို့၊ ရှေ့ဆုံး ၂ ခုကို နှိုင်းယှဉ်ပြီး အငယ်ကို အရင်ထုတ်ရုံ ဖြစ်ပါတယ် —

နှိုင်းယှဉ်	အငယ်ကို ထုတ်	ရလဒ်
`2` vs `1`	`1`	`[1]`
`2` vs `4`	`2`	`[1, 2]`
`5` vs `4`	`4`	`[1, 2, 4]`
`5` (ကျန်)	`5`	`[1, 2, 4, 5]`

void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return; // Base Case: element ၁ ခု (သို့) ၀ ခုသာ ကျန် → စီပြီးသား

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);       // ဘယ်ခြမ်း စီသည်
    mergeSort(arr, mid + 1, right);  // ညာခြမ်း စီသည်
    merge(arr, left, mid, right);    // စီပြီးသား ၂ ခြမ်းကို ပြန်ပေါင်းသည်
}

void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    // ၂ ခြမ်းကို နှိုင်းယှဉ်ပြီး အငယ်ကို အရင်ထည့်သည်
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++]; // <= က stability ထိန်းသည်
        else temp[k++] = arr[j++];
    }
    // ကျန်တဲ့ element တွေ ထည့်သည်
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    // ပေါင်းပြီးသား result ကို မူလ array ထဲ ပြန်ကူးသည်
    System.arraycopy(temp, 0, arr, left, temp.length);
}

ဘာကြောင့် $O(n \log n)$ လဲ? array ကို တစ်ဝက်စီ ခွဲတဲ့အတွက် အလွှာ (level) $\log n$ ခု ရှိပါတယ်။ အလွှာတစ်ခုစီမှာ element အားလုံး ( $n$ ခု) ကို merge လုပ်ရတဲ့အတွက် $O(n)$ ကြာသည်။ စုစုပေါင်း $O(n \log n)$ ဖြစ်ပါတယ်။

အားသာချက်: Merge Sort ဟာ Stable ဖြစ်ပြီး worst case မှာတောင် $O(n \log n)$ အာမခံပါတယ် (Quick Sort လို worst case မရှိ)။ Linked List စီတာ၊ ဒါမှမဟုတ် memory ထဲ မဆံ့တဲ့ data ကြီးကို file နဲ့ ပိုင်းခွဲ စီတဲ့ External Sorting အတွက် အကောင်းဆုံး ဖြစ်ပါတယ်။
အားနည်းချက်: Merge လုပ်ဖို့ array အပို ( $O(n)$ extra space) လိုပါတယ်။

Quick Sort

Quick Sort ဟာ Merge Sort နဲ့ ဆန့်ကျင်ဘက် — ခွဲတဲ့အပိုင်းမှာ အလုပ်လုပ်ပြီး၊ ပေါင်းတဲ့အပိုင်းမှာ ဘာမှ မလုပ်ရ သည့် နည်းလမ်း ဖြစ်ပါတယ်။

Element တစ်ခုကို Pivot အဖြစ် ရွေးပြီး၊ pivot ထက် ငယ်တာတွေကို ဘယ်ဘက်၊ ကြီးတာတွေကို ညာဘက် ခွဲ (partition) ထားပါတယ်။

ဒီ partition ပြီးတဲ့အခါ pivot က သူ့ နေရာအမှန် ရောက်သွား ပါပြီ။ ပြီးတော့ ဘယ်ခြမ်းနဲ့ ညာခြမ်းကို သီးခြားစီ ဒီအတိုင်း ထပ်လုပ်သွားပါတယ်။

[5, 2, 8, 1, 9, 3] မှာ pivot = 3 (နောက်ဆုံး element) ရွေးပြီး partition လုပ်တာ —

i ရဲ့ role: i က "pivot ထက်ငယ်တဲ့ element တွေ စုထားတဲ့ zone ရဲ့ နောက်ဆုံး index" ဖြစ်ပါတယ်။ စတင်တဲ့အချိန်မှာ zone က အလွတ် ဖြစ်တဲ့အတွက် i = -1 (array ထဲ မရောက်သေးတဲ့ မြောက်ဘက် edge) မှ စပါတယ်။ pivot ထက်ငယ်တဲ့ element တစ်ခု တွေ့တိုင်း i တိုးပြီး ထိုး element ကို zone ထဲ ဆွဲယူပါတယ်။ loop ပြီးသောအခါ index 0 ကနေ i ကြားက element အားလုံး pivot ထက် ငယ်ပါတယ်။ i = -1 မှ စပါတယ်

Step	j	arr[j]	arr[j] < pivot (3)?	လုပ်ဆောင်ချက်	Array အခြေအနေ	i
စမှတ်	—	—	—	—	`[5, 2, 8, 1, 9, 3]`	-1
1	0	5	No	ဘာမှ မလုပ်	`[5, 2, 8, 1, 9, 3]`	-1
2	1	2	Yes	i++→0, swap(0,1)	`[2, 5, 8, 1, 9, 3]`	0
3	2	8	No	ဘာမှ မလုပ်	`[2, 5, 8, 1, 9, 3]`	0
4	3	1	Yes	i++→1, swap(1,3)	`[2, 1, 8, 5, 9, 3]`	1
5	4	9	No	ဘာမှ မလုပ်	`[2, 1, 8, 5, 9, 3]`	1
ပြီး	—	—	—	swap(i+1=2, high=5)	`[2, 1, 3, 5, 9, 8]`	1

Pivot 3 က index 2 တွင် သူ့နေရာအမှန် ရောက်သွားပြီ
ဘယ်ခြမ်း [2, 1] နဲ့ ညာခြမ်း [5, 9, 8] ကို သီးခြားစီ ထပ်လုပ်သည်

void quickSort(int[] arr, int low, int high) {
    if (low >= high) return; // Base Case: element ၁ ခု (သို့) ၀ ခု

    int pivotIndex = partition(arr, low, high); // pivot ကို correct position တွင် ထားသည်
    quickSort(arr, low, pivotIndex - 1);  // ဘယ်ခြမ်း (ပိုသေး)
    quickSort(arr, pivotIndex + 1, high); // ညာခြမ်း (ပိုကြီး)
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; // နောက်ဆုံး element ကို pivot အဖြစ်ရွေးသည်
    int i = low - 1;       // "ငယ်တာတွေရဲ့ boundary (နယ်နိမိတ်)"

    for (int j = low; j < high; j++) {
        // pivot ထက် ငယ်ရင် ဘယ်ဘက်ပိုင်းသို့ ရွှေ့သည်
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    // pivot ကို "ငယ်တာ" နဲ့ "ကြီးတာ" အကြား မှန်ကန်တဲ့နေရာ ထားသည်
    int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
    return i + 1;
}

Pivot ရွေးချယ်ခြင်း ဘာကြောင့် အရေးကြီးသလဲ? Pivot က partition ၂ ခြမ်းကို ညီညီ ခွဲပေးရင် အကောင်းဆုံး ( $O(n \log n)$ ) ဖြစ်ပါတယ်။ ဒါပေမယ့် မကောင်းရွေးမိရင် — ဥပမာ စီပြီးသား array [1,2,3,4,5] မှာ အမြဲ နောက်ဆုံးကို pivot ရွေးရင် — ခြမ်းတစ်ခုက အလွတ်၊ တစ်ခြမ်းက ကျန်အကုန် ဖြစ်ပြီး $O(n^2)$ ဆုတ်ယုတ်သွားပါတယ်။ ဒါကြောင့် လက်တွေ့မှာ —

Pivot ကို random ရွေးခြင်း၊

"median-of-three" (ပထမ၊ အလယ်၊ နောက်ဆုံး ၃ ခုရဲ့ အလယ်ကို ရွေး) နည်း — တို့ကို သုံးကြပါတယ်။

အားသာချက်: In-place ( $O(\log n)$ recursion stack သာ) ဖြစ်ပြီး cache-friendly (ဘေးချင်းကပ် memory ကို သုံး) သလို memory လည်း သက်သာတဲ့အတွက် လက်တွေ့ workload အများစုမှာ Merge Sort ထက် မကြာခဏ ပိုမြန် လေ့ရှိပါတယ်။ Java ရဲ့ primitive array sort (Arrays.sort(int[])) ဟာ Dual-Pivot Quicksort ကို သုံးပြီး၊ object array sort (Arrays.sort(Object[])) ကတော့ stable ဖြစ်တဲ့ Timsort ကို သုံးပါတယ်။
အားနည်းချက်: Worst case $O(n^2)$ ဖြစ်နိုင်ပြီး၊ Stable မဟုတ်ပါ။

Heap Sort

Heap Sort ဟာ data ကို Heap ဆိုတဲ့ tree structure အဖြစ် အသုံးချတဲ့ နည်းလမ်း ဖြစ်ပါတယ်။ Max-heap ဆိုတာ "မိဘ node က သားသမီး node ထက် အမြဲ ကြီးတယ်" ဆိုတဲ့ စည်းမျဉ်းရှိတဲ့ binary tree ဖြစ်လို့၊ အကြီးဆုံး element က အမြဲ ထိပ် (root) မှာ ရှိပါတယ်။

Heap Sort က ဒီ feature ကို အသုံးချပါတယ် —

Array ကို max-heap အဖြစ် တည်ဆောက်သည်။
ထိပ်က အကြီးဆုံးကို နောက်ဆုံးနေရာနဲ့ လဲ၊ heap အရွယ် ၁ ခု လျှော့။
ထိပ်မှာ heap rule ပျက်သွားလို့ ပြန်ချိန်ညှိ (heapify) သည်။

(Heap structure ရဲ့ အသေးစိတ်ကို အခန်း ၁၂ မှာ ဆက်လေ့လာပါမယ်။ ဒီနေရာမှာ idea ကိုသိအောင် ပြောပြထားခြင်း ဖြစ်ပါသည်)

void heapSort(int[] arr) {
    int n = arr.length;
    // Step 1: array ကို max-heap အဖြစ် တည်ဆောက်သည် (နောက်ဆုံး မိဘ node ကနေ စ)
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // Step 2: အကြီးဆုံး (root) ကို နောက်ဆုံးနဲ့ လဲ၊ heap အရွယ် လျှော့ပြီး ပြန်ချိန်ညှိ
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
        heapify(arr, i, 0);
    }
}

// node i ကို သူ့ subtree အတွင်း မှန်ကန်တဲ့နေရာ ဆင်းသွားအောင် ချိန်ညှိသည်
void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1, right = 2 * i + 2; // array ထဲ child တွေရဲ့ index
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
        heapify(arr, n, largest); // အောက်ကို ဆက်ချိန်ညှိသည်
    }
}

အားသာချက်: In-place ( $O(1)$ extra space) ဖြစ်ပြီး worst case မှာတောင် $O(n \log n)$ အာမခံပါတယ်။ Quick Sort လို worst case ပြဿနာ မရှိဘဲ memory လည်း သက်သာတဲ့အတွက် memory အကန့်အသတ်ရှိတဲ့ system တွေမှာ ကောင်းပါတယ်။
အားနည်းချက်: Stable မဟုတ်သလို၊ heap က memory ထဲ ခုန်ကျော် ဖတ်ရတဲ့အတွက် cache-friendly မဖြစ်ပါ။ ဒါကြောင့် လက်တွေ့မှာ Quick Sort လောက် မမြန်ပါ။

အပိုင်း ၃ — Non-comparison Sorting

အပေါ်က sort တွေအားလုံးဟာ element တွေကို နှိုင်းယှဉ် ပြီး စီတာ ဖြစ်ပါတယ်။ သင်္ချာအရ သက်သေပြထားတာက — နှိုင်းယှဉ်ပြီး စီတဲ့ algorithm ဘယ်ဟာမှ $O(n \log n)$ ထက် မမြန်နိုင်ပါ။ ဒါကို comparison sort lower bound လို့ ခေါ်ပါတယ်။

ဘာကြောင့်လဲ? Element n ခုကို စီနိုင်တဲ့ ဖြစ်နိုင်ခြေ အစီအစဉ် (permutation) က $n!$ မျိုး ရှိပါတယ်။ နှိုင်းယှဉ်မှု တစ်ခုစီက "ကြီးလား/ငယ်လား" အဖြေ ၂ မျိုးပဲ ထွက်လို့၊ ဖြစ်နိုင်ခြေ $n!$ ခုကို ခွဲခြားဖို့ အနည်းဆုံး $\log_2(n!) \approx n \log n$ ကြိမ် နှိုင်းယှဉ်ဖို့ လိုပါတယ်။

ဒါဆို $O(n \log n)$ ထက် ဘယ်လို ပိုမြန်အောင် လုပ်မလဲ? နှိုင်းယှဉ်တာ မလုပ်တော့ဘဲ data ရဲ့ သဘော (ဥပမာ - "integer ဖြစ်တယ်၊ ၀ ကနေ ၁၀၀ ကြားပဲ ရှိတယ်") ကို တိုက်ရိုက် အသုံးချရင် ပိုမြန်အောင် လုပ်နိုင်ပါတယ်။

Counting Sort

Counting Sort ဟာ element တစ်ခုစီ ဘယ်နှစ်ကြိမ် ပါသလဲ ရေတွက် (count) ပြီး၊ အဲ့ count ကို သုံးကာ နေရာချ စီတဲ့ နည်းလမ်း ဖြစ်ပါတယ်။

[2, 5, 3, 0, 2, 3, 0] (range ၀-၅) ကို စီကြည့်ရအောင် —

Step 1 — ရေတွက်:
  value:  0  1  2  3  4  5
  count:  2  0  2  2  0  1     (0 က ၂ ကြိမ်၊ 2 က ၂ ကြိမ်၊ ...)

Step 2 — count အလိုက် ပြန်ဖြန့်:
  0 ကို ၂ ခု → 0, 0
  2 ကို ၂ ခု → 2, 2
  3 ကို ၂ ခု → 3, 3
  5 ကို ၁ ခု → 5
  ရလဒ်: [0, 0, 2, 2, 3, 3, 5]

int[] countingSort(int[] arr, int k) { // k = အကြီးဆုံး တန်ဖိုး
    int[] count = new int[k + 1];
    // Step 1: element တစ်ခုစီ ဘယ်နှစ်ကြိမ် ပါသလဲ ရေတွက်သည်
    for (int num : arr) count[num]++;

    int[] result = new int[arr.length];
    int idx = 0;
    // Step 2: count အလိုက် ငယ်ရာကနေ ကြီးရာ ပြန်ဖြန့်ချသည်
    for (int num = 0; num <= k; num++) {
        while (count[num] > 0) {
            result[idx++] = num;
            count[num]--;
        }
    }
    return result;
}

ဒီနည်းက နှိုင်းယှဉ်တာ လုံးဝ မလုပ်ဘဲ၊ element n ခုနဲ့ range k ကိုသာ ဖြတ်သန်းရလို့ $O(n + k)$ ဖြစ်ပါတယ်။ Range k က n နဲ့ နီးစပ်ရင် ( $k$ မကြီးရင်) ဒါက $O(n)$ နီးပါး ဖြစ်ပါတယ်။

Stability: အပေါ်က ရိုးရှင်းတဲ့ "count လုပ် ပြီး ပြန်ဖြန့်" version က ကိန်းသက်သက်အတွက် အဆင်ပြေပါတယ်။ ဒါပေမယ့် Counting Sort ကို stable ဖြစ်စေဖို့ (object တွေကို field အလိုက် စီတဲ့အခါ၊ ဒါမှမဟုတ် Radix Sort ထဲ သုံးတဲ့အခါ) prefix sum (cumulative count) နဲ့ output array သီးခြား သုံးပြီး ရေးရပါတယ်။

Stable Counting Sort (prefix sum နည်း):

[2, 5, 3, 0, 2, 3, 0] ကို ဥပမာ ယူပြည့်ရအောင် —

Step 1 — count:       index: 0  1  2  3  4  5
                      count: 2  0  2  2  0  1

Step 2 — prefix sum (count[i] += count[i-1]):
                      count: 2  2  4  6  6  7
                      (meaning: 0 ထက် ငယ်/ညီ k ခုက index 0..1 မှာ ရှိမယ်)

Step 3 — နောက်ဆုံးကနေ ရှေ့ဆီ ဖြတ် (stable ဖြစ်ဖို့):
  arr[6]=0 → count[0]=2 → result[1]=0, count[0]--→1
  arr[5]=3 → count[3]=6 → result[5]=3, count[3]--→5
  arr[4]=2 → count[2]=4 → result[3]=2, count[2]--→3
  arr[3]=0 → count[0]=1 → result[0]=0, count[0]--→0
  arr[2]=3 → count[3]=5 → result[4]=3, count[3]--→4
  arr[1]=5 → count[5]=7 → result[6]=5, count[5]--→6
  arr[0]=2 → count[2]=3 → result[2]=2, count[2]--→2

Result: [0, 0, 2, 2, 3, 3, 5]

"နောက်ဆုံးကနေ ရှေ့ဆီ" ဖြတ်ရတဲ့ အကြောင်းရင်း — တန်ဖိုးတူ element တွေ (ဥပမာ 2 ၂ ခု) ကို မူလ array ထဲ နောက်မှာ ရှိတဲ့ဟာကို output ထဲ နောက်မှာ ထားဖို့ ဖြစ်ပါတယ်။ ဒါမှ မူလ relative order မပျက်ပါ။

int[] stableCountingSort(int[] arr, int k) {
    int[] count = new int[k + 1];
    for (int num : arr) count[num]++;

    // prefix sum: count[i] = arr ထဲ i နဲ့ ညီ/ငယ်တဲ့ element ဘယ်နှစ်ခု ရှိသလဲ
    for (int i = 1; i <= k; i++) count[i] += count[i - 1];

    int[] result = new int[arr.length];
    // နောက်ဆုံးကနေ ရှေ့ဆီ ဖြတ်မှ stable ဖြစ်သည်
    for (int i = arr.length - 1; i >= 0; i--) {
        result[--count[arr[i]]] = arr[i];
    }
    return result;
}

သတိ: တန်ဖိုး range k က အလွန်ကြီးရင် (ဥပမာ - ၁ ကနေ သန်းပေါင်းများစွာ၊ ဒါမှမဟုတ် negative/decimal တွေ ပါ) count array က memory အများကြီး ယူသွားလို့ မသင့်တော်တော့ပါ။ "Integer ဖြစ်ပြီး range သေး" တဲ့အခါမှ သုံးပါ။

Radix Sort

Counting Sort က range ကြီးရင် မသုံးနိုင်တဲ့ ပြဿနာကို Radix Sort က ဖြေရှင်းပါတယ်။ ကိန်းတွေကို ဂဏန်းတစ်လုံးချင်း (digit by digit) —နောက်ဆုံး ကနေ ကြီးတဲ့နေရာဆီ — Counting Sort နဲ့ ထပ်ခါ စီသွားတဲ့ နည်းလမ်း ဖြစ်ပါတယ်။ ဂဏန်းတစ်လုံးက ၀-၉ ပဲ ရှိလို့ range သေးပြီး Counting Sort လုပ်လို့ ရပါတယ်။

[170, 45, 75, 90, 2, 802]
ones (နောက်ဆုံးဂဏန်း) အလိုက်  → [170, 90, 2, 802, 45, 75]
tens (ဆယ်လီ) အလိုက်          → [2, 802, 45, 170, 75, 90]
hundreds (ရာလီ) အလိုက်       → [2, 45, 75, 90, 170, 802]   ← စီပြီး

Ones-digit pass အသေးစိတ်: [170, 45, 75, 90, 2, 802] ကို ones digit (နောက်ဆုံးဂဏန်း) အလိုက် stable sort လုပ်ပုံ —

element	ones digit
170	0
45	5
75	5
90	0
2	2
802	2

digit 0 bucket → 170, 90 (မူလ အစီအစဉ်အတိုင်း stable)
digit 2 bucket → 2, 802
digit 5 bucket → 45, 75
ပြန်ဆက် → [170, 90, 2, 802, 45, 75]

ဒီ ones-digit pass မှာ stable ဖြစ်မှ digit 0 bucket ထဲ 170 က 90 ရှေ့မှာ ကျန်ပါတယ်။ မူလ order မပျက်ဘဲ ထိန်းထားတဲ့အတွက် tens, hundreds pass တွေ ဆက်လုပ်ရင် မှန်ကန်သော ရလဒ် ရပါတယ်။

ဂဏန်း d လုံးရှိရင် Counting Sort ကို d ကြိမ် လုပ်ရလို့ $O(d \times (n + k))$ ဖြစ်ပါတယ်။ Radix Sort အလုပ်လုပ်ဖို့ digit-level Counting Sort က stable ဖြစ်ဖို့ မဖြစ်မနေ လိုအပ်ပါတယ် — မဟုတ်ရင် ရှေ့ digit တွေ စီထားတာ ပျက်သွားမှာ ဖြစ်ပါတယ်။

Bucket Sort

Bucket Sort ဟာ တန်ဖိုးတွေကို bucket (အကန့်) အများ ထဲ ခွဲဝေထည့်ပြီး၊ bucket တစ်ခုစီကို သီးခြားစီ (များသောအားဖြင့် Insertion Sort နဲ့) စီကာ နောက်ဆုံး bucket တွေကို အစဉ်လိုက် ပြန်ဆက်တဲ့ နည်းလမ်း ဖြစ်ပါတယ်။

[0.78, 0.17, 0.39, 0.26, 0.72, 0.94]   (၀ ကနေ ၁ ကြား decimal)
bucket ၁၀ ခု ခွဲ (တန်ဖိုး × 10):
  bucket[1]: 0.17
  bucket[2]: 0.26
  bucket[3]: 0.39
  bucket[7]: 0.78, 0.72  → သီးခြားစီ → 0.72, 0.78
  bucket[9]: 0.94
ပြန်ဆက်: [0.17, 0.26, 0.39, 0.72, 0.78, 0.94]

Data က အပိုင်းအခြားတစ်ခုအတွင်း ညီညာ ဖြန့်ကျက် (uniformly distributed) နေတဲ့အခါ bucket တစ်ခုစီမှာ element နည်းနည်းပဲ ရှိလို့ $O(n)$ နီးပါး ဖြစ်ပါတယ်။ ဒါပေမယ့် တန်ဖိုးတွေ bucket တစ်ခုထဲ စုနေရင်တော့ $O(n^2)$ ဆုတ်နိုင်ပါတယ်။

အကျဉ်းချုပ်: Non-comparison sort တွေဟာ "data က integer လား၊ range သေးလား၊ ညီညာဖြန့်နေလား" ဆိုတဲ့ အခြေအနေ ပြည့်မှ သုံးနိုင်ပါတယ်။ အထွေထွေ data (object, string နဲ့ custom rule, range မသိ) အတွက်တော့ Quick/Merge/Heap Sort ပဲ သုံးရပါမယ်။

Object များကို Field အလိုက် စီခြင်း (Custom Comparator)

လက်တွေ့ development မှာ ကိန်းသက်သက် မဟုတ်ဘဲ object (user, product, order) တွေကို field တစ်ခုခုအလိုက် စီရတာ အများဆုံးပါ။ ဒီအတွက် sort algorithm ကိုယ်တိုင် မရေးဘဲ၊ built-in sort ကို Custom Comparator နဲ့ သုံးပါတယ်။ Comparator ဆိုတာ "element ၂ ခု ဘယ်ဟာ အရင်လာရမလဲ" ဆုံးဖြတ်ပေးတဲ့ rule (function) ဖြစ်ပါတယ်။

Comparator တစ်ခုက a, b ၂ ခုကို ယူပြီး —

negative ပြန်ရင် → a က ရှေ့လာရမည်၊
positive ပြန်ရင် → b က ရှေ့လာရမည်၊
0 ပြန်ရင် → အတူတူ (အစီအစဉ် မပြောင်း) — ဆိုပြီး ဆုံးဖြတ်ပါတယ်။

import java.util.Arrays;
import java.util.Comparator;

class User {
    String name;
    int age;
    User(String name, int age) { this.name = name; this.age = age; }
}

class Solution {
    void sortUsers(User[] users) {
        // age အငယ်ကနေ အကြီး (ascending) စီသည်
        Arrays.sort(users, Comparator.comparingInt(u -> u.age));

        // Multi-field: age အလိုက် အရင်စီ၊ age တူရင်မှ name အလိုက် စီသည်
        Arrays.sort(users, Comparator
            .comparingInt((User u) -> u.age)
            .thenComparing(u -> u.name));

        // age အကြီးကနေ အငယ် (descending) စီသည်
        Arrays.sort(users, Comparator.comparingInt((User u) -> u.age).reversed());
    }
}

Stability ဘာကြောင့် ဒီနေရာ အရေးကြီးသလဲ? Java ရဲ့ object sort (Arrays.sort(Object[])) ဟာ Timsort (Merge Sort + Insertion Sort ပေါင်းစပ်ထား၊ stable) ကို သုံးပါတယ်။ Stable ဖြစ်လို့ "name အလိုက် အရင်စီ၊ ပြီးမှ age အလိုက် ထပ်စီ" ဆိုတဲ့ chained sort ကိုလည်း မှန်ကန်စွာ လုပ်နိုင်ပါတယ်။ (Primitive int[] တွေအတွက်တော့ Dual-Pivot Quick Sort ကို သုံးပါတယ် — primitive မှာ တန်ဖိုးတူ element တွေ ခွဲမရလို့ stability က အရေးမကြီးပါ။)

Real-world Examples

Sorting ဟာ backend, frontend, data processing အားလုံးမှာ နေ့စဉ် ကြုံရတဲ့ လုပ်ငန်း ဖြစ်ပါတယ်။

Sort users by created date — user list ကို အသစ်ဆုံး/အဟောင်းဆုံး အလိုက် ပြသခြင်း။
Sort products by price — e-commerce မှာ "Price: Low to High" filter။
Sort transactions by amount — ငွေပမာဏ အကြီးဆုံး transaction တွေ ရှာခြင်း။
Sort leaderboard by score — game ranking ကို score အလိုက် စီခြင်း (score တူရင် အချိန်အလိုက် ဆက်စီ)။
Sort logs by timestamp — log entry တွေကို အချိန်အလိုက် စီပြီး debug လုပ်ခြင်း။

ဒီ use case တွေအတွက် language ရဲ့ built-in sort ( $O(n \log n)$ ) ကို custom comparator နဲ့ သုံးတာ အကောင်းဆုံး ဖြစ်ပါတယ်။ ကိုယ်တိုင် sort algorithm ရေးစရာ မလိုပါ။ ဒါပေမယ့် မေးရမယ့် မေးခွန်းက — "ဒီ sort က stable ဖြစ်လား?" ဆိုတာပါ။ Programming language အများစုမှာ optimize လုပ်ထားတဲ့ built-in sort ပါပေမယ့်၊ stable ဖြစ်မဖြစ်က language နဲ့ data type ပေါ်မူတည် ပါတယ် (ဥပမာ - Java မှာ object sort က stable ဖြစ်ပေမယ့် primitive int[] sort က မဟုတ်ပါ)။ Multi-field sorting လုပ်မယ်ဆိုရင် stable ဖြစ်တာ အရေးကြီးလို့ အရင် စစ်ဆေးသင့်ပါတယ်။

Timsort: Python နဲ့ Java (object sort) တို့ဟာ Timsort (သို့) Timsort-inspired algorithm ကို သုံးကြပါတယ်။ Timsort ဟာ Merge Sort နဲ့ Insertion Sort ကို ပေါင်းစပ်ထားပြီး stable ဖြစ်ပါတယ်။ Data ဟာ အပိုင်းအားဖြင့် စီပြီးသား (partially sorted) ဖြစ်တဲ့အခါ — real-world data အများစုက ဒီလို ဖြစ်တတ် — အလွန်မြန်ပါတယ်။ ဒါက အပေါ်မှာ ပြောခဲ့တဲ့ Insertion Sort ရဲ့ "nearly sorted data မှာ မြန်တယ်" ဆိုတဲ့ အချက်ကို real-world system တွေမှာ အသုံးချထားတာ ဖြစ်ပါတယ်။

Questions

Sorting concept တွေကို လက်တွေ့ ပြဿနာတွေနဲ့ ချိတ်ဆက်ပြီး အသုံးချနည်း ၅ မျိုးကို တစ်ဆင့်ချင်း လေ့လာကြည့်ရအောင်။ မေးခွန်းတွေဟာ "sort ကို ဘယ်လို အသုံးချမလဲ" ဆိုတဲ့ pattern ကို ဖော်ပြထားပါတယ်။

၁။ Merge Sorted Array

စီပြီးသား (ascending) array ၂ ခု nums1 နဲ့ nums2 ပေးထားသည်။ nums1 မှာ nums2 ကို ဆံ့အောင် နေရာ (m + n အရွယ်) ထားပြီးသား ဖြစ်သည် (နောက်ပိုင်းမှာ 0 တွေ ဖြည့်ထား)။ နှစ်ခုကို တစ်ခုတည်း စီပြီးသား array အဖြစ် ပေါင်းပါ။ nums1 ထဲမှာတင် (in-place) ပြုလုပ်ပါ။

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

ရှင်းလင်းချက်

နှစ်ခုစလုံး စီပြီးသား ဖြစ်လို့ Merge Sort ရဲ့ merge အဆင့် ကို တိုက်ရိုက် သုံးနိုင်ပါတယ်။ ဒါပေမယ့် အရှေ့ကနေ စီရင် nums1 ရဲ့ မူလ တန်ဖိုးတွေ ဖျက်မိနိုင်ပါတယ် (ဥပမာ - position 0 ကို ရေးလိုက်ရင် nums1[0]=1 ပျောက်သွားမယ်)။

ဒါကို အနောက်ဆုံး (အကြီးဆုံး) ကနေ စပြီး ဖြည့်လိုက်ရင် ဖြေရှင်းနိုင်ပါတယ်။ nums1 ရဲ့ အနောက်ပိုင်းက 0 တွေ (နေရာလွတ်) ဖြစ်လို့ ရေးချလို့ ရပါတယ်။

Pointer i က nums1 ရဲ့ နောက်ဆုံး တကယ့်တန်ဖိုး (m-1)၊ j က nums2 ရဲ့ နောက်ဆုံး (n-1)။
k က ဖြည့်မယ့်နေရာ (အနောက်ဆုံး)။
i, j ၂ ခုထဲက အကြီးကို k နေရာမှာ ထား၊ ပြီးရင် pointer တွေ နောက်ဆုတ်။

Time Complexity: $O(m + n)$ - element အားလုံးကို တစ်ကြိမ်စီ ကြည့်သောကြောင့်။
Space Complexity: $O(1)$ - nums1 ထဲမှာတင် ပြုလုပ်လို့ memory အပို မလို။

Java Solution

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;      // nums1 ၏ နောက်ဆုံး တကယ့်တန်ဖိုး
        int j = n - 1;      // nums2 ၏ နောက်ဆုံး
        int k = m + n - 1;  // ဖြည့်မယ့် နေရာ (အနောက်ဆုံး)

        while (j >= 0) {
            // ၂ ခုထဲက အကြီးကို အနောက်ဆုံးနေရာ ထားသည်
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        // nums1 ဘက် ကျန်ရင် နေရာမှန်ပြီးသား ဖြစ်လို့ ဆက်မလုပ်တော့
    }
}

၂။ Sort Colors

0 (အနီ), 1 (အဖြူ), 2 (အပြာ) တွေပဲ ပါတဲ့ array nums ပေးထားသည်။ အရောင်တူတွေ စုနေအောင်၊ 0 → 1 → 2 အစီအစဉ်အတိုင်း in-place စီပါ။ Library sort မသုံးဘဲ ပြုလုပ်ပါ။

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

ရှင်းလင်းချက်

တန်ဖိုး ၃ မျိုးပဲ ရှိလို့ Counting Sort လုပ်လို့ ရပါတယ် (count ပြီး ပြန်ဖြန့်)။ ဒါပေမယ့် အဲ့ဒါက array ကို ၂ ပတ် ဖြတ်ရပါတယ်။ ဒီ ပြဿနာက တစ်ပတ်တည်း (one pass) နဲ့ ဖြေနိုင်ပါတယ်။

ဒါက Dutch National Flag ပြဿနာ (Edsger Dijkstra တင်ပြခဲ့) ဖြစ်ပြီး pointer ၃ ခု သုံးပါတယ် —

low — 0 တွေ စုထားမယ့် boundary (နယ်နိမိတ်) (low ဘယ်ဘက်မှာ 0 တွေ ရှိ)။
high — 2 တွေ စုထားမယ့် boundary (နယ်နိမိတ်) (high ညာဘက်မှာ 2 တွေ ရှိ)။
mid — လက်ရှိ ကြည့်နေတဲ့ နေရာ။

mid က element ကို ကြည့်ပြီး —

0 ဆို → low နဲ့ လဲ၊ low နဲ့ mid ၂ ခုလုံး တိုး။
1 ဆို → နေရာမှန်ပြီး → mid သာ တိုး။
2 ဆို → high နဲ့ လဲ၊ high လျှော့ (လဲထားတဲ့ element ကို ပြန်စစ်ဖို့ mid မတိုး)။

[2, 0, 2, 1, 1, 0] ကို တစ်ဆင့်ချင်း ကြည့်ရအောင် —

Step	nums[mid]	လုပ်ဆောင်ချက်	Array	low	mid	high
စမှတ်	—	—	`[2, 0, 2, 1, 1, 0]`	0	0	5
1	2	swap(mid=0, high=5), high--	`[0, 0, 2, 1, 1, 2]`	0	0	4
2	0	swap(low=0, mid=0), low++, mid++	`[0, 0, 2, 1, 1, 2]`	1	1	4
3	0	swap(low=1, mid=1), low++, mid++	`[0, 0, 2, 1, 1, 2]`	2	2	4
4	2	swap(mid=2, high=4), high--	`[0, 0, 1, 1, 2, 2]`	2	2	3
5	1	mid++	`[0, 0, 1, 1, 2, 2]`	2	3	3
6	1	mid++	`[0, 0, 1, 1, 2, 2]`	2	4	3
ပြီး	—	mid > high → ရပ်	`[0, 0, 1, 1, 2, 2]`	—	—	—

Step 1 နဲ့ Step 4 မှာ mid မတိုးတဲ့ အကြောင်းရင်း — high ဘက်ကနေ လဲလာတဲ့ element ဘာတန်ဖိုးရှိမှန်း မသိသေးတဲ့အတွက် ထဲ element ကို ထပ်စစ်ဖို့ mid ကို တိုး မချနေဘဲ ထားတာ ဖြစ်ပါတယ်။

Time Complexity: $O(n)$ - တစ်ပတ်တည်း။
Space Complexity: $O(1)$ - in-place။

Java Solution

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                low++; mid++;
            } else if (nums[mid] == 1) {
                mid++; // 1 က အလယ်မှာ ရှိပြီးသား
            } else {
                swap(nums, mid, high);
                high--; // လဲထားတဲ့ တန်ဖိုးကို ပြန်စစ်ရန် mid မတိုး
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
    }
}

၃။ Top K Frequent Elements

ကိန်းပြည့် array nums နဲ့ ကိန်း k ပေးထားသည်။ Frequency အများဆုံး (most frequent) ဖြစ်တဲ့ element k ခုကို ပြန်ပါ။

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1, 2]
Explanation: 1 က ၃ ကြိမ်၊ 2 က ၂ ကြိမ်၊ 3 က ၁ ကြိမ် ပါသည်။

ရှင်းလင်းချက်

ဖြေနည်း ၃ ဆင့် ရှိပါတယ် —

Count: Hash Map (အခန်း ၄) နဲ့ element တစ်ခုစီရဲ့ frequency ကို ရေတွက်သည် — {1:3, 2:2, 3:1}။
Sort by frequency: frequency အလိုက် စီရမယ်။ Frequency ၏ တန်ဖိုးက အများဆုံး n (array length) ပဲ ဖြစ်နိုင်လို့၊ frequency ကို index အဖြစ် သုံးတဲ့ Bucket Sort idea နဲ့ sort လုပ်စရာ မလိုဘဲ $O(n)$ နဲ့ ရပါတယ်။
Collect: frequency အများဆုံး (bucket နောက်ဆုံး) ကနေ စပြီး k ခု ကောက်ယူသည်။

bucket[f] = frequency f အတိအကျ ရှိတဲ့ element တွေ စာရင်း ဖြစ်ပါတယ်။

ဘာကြောင့် Bucket Sort idea သုံးသလဲ? ပုံမှန် sort လုပ်ရင် $O(n \log n)$ ဖြစ်ပေမယ့်၊ frequency က 1 ကနေ n ကြားသာ ဖြစ်လို့ index အဖြစ် တိုက်ရိုက် သုံးနိုင်ပြီး $O(n)$ ရအောင် လုပ်နိုင်ပါတယ်။

Time Complexity: $O(n)$ - count + bucket fill + collect။
Space Complexity: $O(n)$ - map နှင့် bucket အတွက်။

Java Solution

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Step 1: frequency ရေတွက်သည်
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // Step 2: frequency ကို index အဖြစ် bucket ထဲ ထည့်သည်
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int num : count.keySet()) {
            int freq = count.get(num);
            if (bucket[freq] == null) bucket[freq] = new ArrayList<>();
            bucket[freq].add(num);
        }

        // Step 3: frequency အများဆုံး (နောက်ဆုံး bucket) ကနေ k ခု ကောက်သည်
        int[] result = new int[k];
        int idx = 0;
        for (int f = bucket.length - 1; f >= 0 && idx < k; f--) {
            if (bucket[f] != null) {
                for (int num : bucket[f]) {
                    result[idx++] = num;
                    if (idx == k) break;
                }
            }
        }
        return result;
    }
}

မှတ်ချက်: ဒီပြဿနာကို Heap (Priority Queue) နဲ့လည်း $O(n \log k)$ နဲ့ ဖြေနိုင်ပါတယ်။ Heap က "အကြီးဆုံး/အငယ်ဆုံး k ခု" ပြဿနာတွေအတွက် အသုံးဝင်ပြီး၊ အခန်း ၁၂ မှာ ဆက်လေ့လာပါမယ်။

၄။ Sort Array by Custom Rule (Largest Number)

အပြုသဘော ကိန်းပြည့် array nums ပေးထားသည်။ သူတို့ကို ဆက်စပ်ရေးရင် အကြီးဆုံး ဂဏန်း (largest number) ရအောင် စီပြီး string အဖြစ် ပြန်ပါ။

Example 1:

Input: nums = [3, 30, 34, 5, 9]
Output: "9534330"
Explanation: ဆက်စပ်ရေးရင် အကြီးဆုံး ဖြစ်အောင် 9, 5, 34, 3, 30 အစီအစဉ်ဖြင့် စီသည်။

ရှင်းလင်းချက်

ဒါက Custom Comparator ရဲ့ စွမ်းအား ပြတဲ့ ပြဿနာ ဖြစ်ပါတယ်။ ကိန်းတန်ဖိုး အလိုက် ရိုးရိုး မစီနိုင်ပါ (ဥပမာ - 30 > 3 ပေမယ့် "3" က ရှေ့လာရင် ပိုကြီးတဲ့ "330" ရတယ်)။ ဒါကြောင့် ဆက်စပ်လိုက်ရင် ဘယ်ဟာ ပိုကြီးလဲ ဆိုတဲ့ rule နဲ့ စီရပါမယ်။

a နဲ့ b ၂ ခုအတွက် a+b နဲ့ b+a (string concatenation) ကို နှိုင်းယှဉ်သည်။
"3"+"30" = "330" vs "30"+"3" = "303" → 330 > 303 ဖြစ်လို့ 3 က 30 ရှေ့ လာရမည်။

ဒီ comparator က element ၂ ခုကြားက မှန်ကန်တဲ့ အစီအစဉ်ကို ဆုံးဖြတ်ပေးပြီး၊ sort က element အားလုံးကို အဲ့ rule အတိုင်း စီပေးပါတယ်။

Edge case: array အကုန် 0 ဖြစ်နေရင် (ဥပမာ [0, 0]) ရလဒ်က "00" မဟုတ်ဘဲ "0" ဖြစ်ရမယ်။ ဒါကြောင့် ရှေ့ဆုံးက "0" ဖြစ်ရင် "0" ပဲ ပြန်ပါ။

Time Complexity: $O(n \log n \cdot d)$ - sort လုပ်ရာတွင် string နှိုင်းယှဉ်မှု ( $d$ = digit length) ပါဝင်သောကြောင့်။
Space Complexity: $O(n)$ - string array အတွက်။

Java Solution

import java.util.*;

class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }

        // Custom rule: ဆက်စပ်ရင် ကြီးတဲ့ဟာ ရှေ့လာသည်
        Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));

        // အကုန် "0" ဖြစ်နေရင် "0" ပြန်သည် (ဥပမာ [0,0] → "0")
        if (strs[0].equals("0")) return "0";

        StringBuilder sb = new StringBuilder();
        for (String s : strs) sb.append(s);
        return sb.toString();
    }
}

၅။ Merge Intervals

Interval (အပိုင်းအခြား) တွေ ပါတဲ့ array intervals ပေးထားသည် ([start, end])။ ထပ်နေ (overlapping) တဲ့ interval တွေကို ပေါင်းစည်းပြီး၊ ထပ်မနေတဲ့ interval list ကို ပြန်ပါ။

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] နဲ့ [2,6] က ထပ်နေ (2 ≤ 3) လို့ [1,6] အဖြစ် ပေါင်းသည်။

ရှင်းလင်းချက်

ဒါက Sorting ကို preprocessing အဖြစ် အသုံးချတဲ့ classic ပြဿနာ ဖြစ်ပါတယ်။ Interval တွေ ရောနေတဲ့အခါ ဘယ်ဟာတွေ ထပ်နေလဲ ရှာဖို့ ခက်ပါတယ်။ ဒါပေမယ့် start အလိုက် အရင်စီ လိုက်ရင်၊ ထပ်နေတဲ့ interval တွေဟာ ဘေးချင်းကပ် နေမှာ ဖြစ်လို့ တစ်ပတ်တည်း လိုက်ပေါင်းနိုင်ပါတယ်။

intervals ကို start အလိုက် sort လုပ်သည်။
လက်ရှိ interval ရဲ့ start က ရှေ့ (current) interval ရဲ့ end ထက် ငယ်/ညီ ရင် (ထပ်နေရင်) → current ရဲ့ end ကို ၂ ခုထဲက အကြီးအဖြစ် ချဲ့သည်။
မထပ်ရင် → current ကို result ထဲ ထည့်ပြီး interval အသစ်အဖြစ် ဆက်သည်။

Time Complexity: $O(n \log n)$ - sort က အဓိက ကုန်ကျစရာ (ပေါင်းတဲ့ loop က $O(n)$ သာ)။
Space Complexity: $O(n)$ - result list အတွက်။

Java Solution

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        // start အလိုက် စီသည် (preprocessing)
        // a[0] - b[0] သုံးရင် ကိန်းကြီးတွေမှာ integer overflow ဖြစ်နိုင်လို့ Integer.compare သုံးသည်
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();
        int[] current = intervals[0];
        result.add(current);

        for (int[] interval : intervals) {
            if (interval[0] <= current[1]) {
                // ထပ်နေသည် → end ကို ချဲ့သည်
                current[1] = Math.max(current[1], interval[1]);
            } else {
                // မထပ် → interval အသစ် စသည်
                current = interval;
                result.add(current);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

မှတ်ချက်: Interval ပြဿနာတွေ (booking, meeting room, schedule) အများစုဟာ start သို့မဟုတ် end အလိုက် စီခြင်း ကနေ စတင်ဖြေရှင်းလေ့ ရှိပါတယ်။ ဒီအကြောင်းကို အခန်း ၂၁ (Intervals) မှာ အသေးစိတ် ဆက်လေ့လာပါမယ်။