You are not allowed to perform this action

مرتب‌سازی درغامی

الگوریتم (Inserge-Sort(A که هدف‌ش مرتّب‌سازی آرایه‌ی $A$ است، بدین صورت است:

  1. $n$ $\leftarrow$ Length($A$);
  2. $k$ $\leftarrow$ Random($1$, $\lfloor\frac{n}{2}\rfloor$);
  3. Insertion-Sort($A[1..k]$);
  4. Inserge-Sort($A[k+1..n]$);
  5. Merge($A[1..k], A[k+1..n]$);

که منظور از $A[x..y]$، زیرآرایه‌ی شامل $A[x]$ تا $A[y]$ است و تابع ($y$,$x$)Random یک عدد تصادفی در بازه‌ی $[x,y]$ برمی‌گرداند.

رابطه‌ی بازگشتی زمان اجرای این الگوریتم را بر حسب $n$ نوشته و زمان اجرای متوسّط آن را صریحاً تحلیل کنید.