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

<WRAP :en> 

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

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

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

  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]