سوال ۶۶ کنکور ارشد علوم کامپیوتر ۱۳۹۸

This is the classic coarsening of merge sort (CLRS Problem 2-1): once a subarray drops to a fixed small size $k$ (here $k=20$), stop recursing and sort that block with insertion sort instead. The crucial point is that $k=20$ is a constant, independent of $n$.

Cost of the insertion-sort phase. Insertion sort on a block of size $k$ costs $\Theta(k^{2})$ in the worst case. There are $\tfrac{n}{k}$ such blocks, so the total cost of sorting all blocks is

$\frac{n}{k}\cdot \Theta(k^{2}) = \Theta(nk).$

Since $k=20$ is constant, $\Theta(nk)=\Theta(n)$.

Cost of the merging phase. After the blocks are sorted, merge sort still merges them back up the tree. Starting from blocks of size $k$ up to the full array of size $n$, the number of merge levels is

$\log_2\!\left(\frac{n}{k}\right)=\log_2 n-\log_2 k=\Theta(\log n),$

and each level does $\Theta(n)$ work merging. So merging costs $\Theta(n\log n)$.

Total.

$T(n)=\underbrace{\Theta(n)}_{\text{insertion blocks}}+\underbrace{\Theta(n\log n)}_{\text{merging}}=\Theta(n\log n).$

The $n\log n$ merging term dominates, so the asymptotic complexity is unchanged from plain merge sort. The answer is option 3, $\Theta(n\log n)$.

Pitfall: The trap answers ($\Theta(n^{2})$, $\Theta(n^{2}\log n)$) come from treating the insertion-sort blocks as if their size grew with $n$. The cutoff size $20$ is a constant, so $\Theta(k^{2})=\Theta(1)$ per block and the quadratic behavior never appears asymptotically. (Coarsening only improves the hidden constant in practice; it never changes the $\Theta$ class.)