Adaptive Merge Sort
คล้าย Merge Sort แตขนาด Initial Sub-list ขึ้นกับ Existing Order ใน List ไม่ใช่คงที่ที่ 1
ตัวอย่าง
List: [16,15,14,13, 9,10,11,12] → 2 Sorted Sub-lists:
Sub-list 1: 16,15,14,13 (Reverse Sorted)
Sub-list 2: 9,10,11,12 (Sorted)
Sub-list 1 Reverse → [13,14,15,16]
Merge 2 Sub-lists → 1 Merge Step → Sorted List
Design Idea
- หา Sub-lists ที่ Sorted แล้ว (Required หรือ Reverse Order)
- ถ้า Reverse → Reverse Sub-list (Swap 1st↔Last, 2nd↔2nd Last...)
- Merge Sub-lists ซ้ำจนเหลือ 1 Sub-list
Analysis
Initial Sub-list Size: Min 2, Max m (m = Elements)
Reverse Sub-list → (m/2) Exchanges ก่อน Merge
Best Case: O(m)
List Sorted หรือ Reverse Sorted แล้ว → 1 Sub-list → No Merge
Detect Sorted: O(m) Comparisons + (m/2) Exchanges (ถ้า Reverse)
T(m) = (m-1) + (m/2) = O(m)
Adaptive แม้ Reverse Sorted!
Space: O(m) Extra (vs Merge Sort)
Worst Case: O(m log m)
No Partial/Total Order → Initial Sub-lists Size = 2
Merge Steps = log m (เหมือน Merge Sort)
T(m) = O(m log m)
สรุป
Adaptive Merge Sort = Natural Merge Sort Variant
Exploit Existing Order → Best Case Linear
Worst Case = Standard Merge Sort
Trade-off: Extra O(m) Space
