مرتب‌سازی ادغامی
Merge SortMerge Sort از Divide and Conquer استفاده می‌کند: Array را تا بخش‌های کوچک تقسیم می‌کند و سپس بخش‌های مرتب را دوباره merge می‌کند.
اول این مفهوم را در ذهن نگه دار
Merge Sort از Divide and Conquer استفاده می‌کند: Array را تا بخش‌های کوچک تقسیم می‌کند و سپس بخش‌های مرتب را دوباره merge می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
مرحله merge خطی است چون هر دو نیمه از قبل مرتب‌اند.
تقسیم حدود log n سطح دارد، پس زمان کل O(n log n) است و نسخه معمول Array حدود O(n) حافظه کمکی می‌خواهد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
ببین هر pass/partition/merge چه بخشی را قطعی می‌کند.
ناحیه‌ای را که دیگر نهایی شده دنبال کن.
تعداد comparison، swap/move و حافظه اضافه را تحلیل کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مرتب‌سازی ادغامی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
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));
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(n log n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- انتخاب را بر اساس اندازه داده، میزان مرتب بودن، بازه key، stable بودن و محدودیت حافظه انجام بده.
کجا معمولاً اشتباه می‌کنیم؟
- فقط Average Big-O را مقایسه نکن.
- stability، in-place بودن، عمق recursion و فرض‌های مربوط به domain را فراموش نکن.
مدل یک پاسخ حرفه‌ای
O(n log n) تضمین‌شده، stable بودن و هزینه حافظه اضافی را باهم بگو. برای Linked List و External Sorting هم الگوریتم طبیعی‌ای است.
مرتب‌سازی ادغامی چه مسئله‌ای را حل می‌کند؟
Merge Sort از Divide and Conquer استفاده می‌کند: Array را تا بخش‌های کوچک تقسیم می‌کند و سپس بخش‌های مرتب را دوباره merge می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(n log n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فقط Average Big-O را مقایسه نکن.