Merge Sort
Merge sort uses divide and conquer: split the array until pieces are trivial, then merge sorted pieces back together.
ابدأ بهذا النموذج الذهني
Merge sort uses divide and conquer: split the array until pieces are trivial, then merge sorted pieces back together.
كيف يعمل، بلا مصطلحات زائدة
The merge step is linear because each side is already sorted.
There are log n levels of splitting, so total time is O(n log n). Standard array implementations use O(n) extra memory.
اقرأ الخوارزمية كسلسلة من القرارات
Understand what one pass/partition/merge guarantees.
Track which region is already finalized.
Reason about comparisons, swaps/moves and extra memory.
Read a tiny input by hand and write down the state after every important operation. For Merge Sort, the goal is to make the invariant visible rather than to memorize code.
function mergeSort(a) {
if (a.length <= 1) return a;
const mid = Math.floor(a.length / 2);
return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}
function merge(left, right) {
const out = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
out.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
return out.concat(left.slice(i), right.slice(j));
}لا تحفظ الصياغة. تتبع الحالة التي تتغير في كل سطر واربطها بالثابت الموضح أعلاه.
O(n log n)
Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.
مناسب لـ
- Choose based on input size, order, key range, stability and memory limits.
ما الذي يسوء عادةً
- Comparing only average Big-O.
- Forgetting stability, in-place behavior, recursion depth or key-domain assumptions.
صيغة إجابة احترافية
Highlight predictable O(n log n), stability, and the extra-memory trade-off. It is also natural for linked lists and external sorting.
What problem does Merge Sort solve?
Merge sort uses divide and conquer: split the array until pieces are trivial, then merge sorted pieces back together.
ماذا يجب أن أذكر عن التعقيد؟
Its typical cost here is O(n log n), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.
ما الخطأ الأكثر شيوعاً؟
Comparing only average Big-O.