سوال ۶۶ کنکور ارشد مهندسی کامپیوتر ۱۴۰۲

الگوریتم مرتب‌سازی ادغام (Megesort) را درنظر بگیرید. به‌جای اینکه آرایه ورودی را به دو قسمت تقریباً مساوی تقسیم کنیم، آن را به m بخش تقسیم می‌کنیم که لزوماً مساوی نیستند (m یک ثابت است.) سپس به‌صورت بازگشتی الگوریتم ادغام اصلاح‌شده را روی هر قسمت اجرا می‌کنیم و m آرایه مرتب‌شده را ادغام می‌کنیم. زمان اجرای الگوریتم ادغام اصلاح‌شده در حالتی که ۲ < m کدام است؟