تخيل عندك كتاب ضخم ومحتاج ترتبه. بدل ما ترتبه كله مرة واحدة:
قسّم المشكلة لمشاكل أصغر
حل كل مشكلة صغيرة (recursively)
ادمج الحلول الصغيرة
ترتيب الدمج - المثال الكلاسيكي
✓ مترتبة!
الـ Merge هو قلب الخوارزمية. بناخد قطعتين مترتبتين وندمجهم:
مثال: دمج [3, 27] مع [9, 43]
💡 الفكرة:
log n: عدد مستويات التقسيم
n: عمليات الـ merge في كل مستوى
أفضل، متوسط، وأسوأ حالة كلهم O(n log n)!
محتاجين array مؤقتة للـ merge
⚠️ مش in-place زي Selection Sort
+ O(log n) للـ call stack
Click "Sort" to see Merge Sort in action.
function mergeSort(arr) {
// Base Case
if (arr.length <= 1) return arr;
// Divide
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
// Combine (Merge)
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i), right.slice(j));
}