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

This is the naive sequential merge of $k$ sorted lists, where a running accumulator is repeatedly merged with the next list.

Merging two sorted lists of sizes $a$ and $b$ costs $\Theta(a+b)$. Each of the $k$ lists holds $\frac{n}{k}$ elements.

After the first $j$ lists have been merged, the accumulator holds $j\cdot\frac{n}{k}$ elements. Merging it with the next list (another $\frac{n}{k}$ elements) costs

$\left(j\cdot\frac{n}{k}+\frac{n}{k}\right)=(j+1)\cdot\frac{n}{k}.$

Summing over the $k-1$ merge steps ($j=1,\dots,k-1$):

$\sum_{j=1}^{k-1}(j+1)\cdot\frac{n}{k}=\frac{n}{k}\sum_{m=2}^{k} m=\frac{n}{k}\left(\frac{k(k+1)}{2}-1\right)=\Theta(nk).$

So the worst-case time is $\Theta(nk)$, i.e. $O(nk)$ — option 4.

Intuitively, the first list's elements get re-scanned in every one of the $\sim k$ merge passes, so the early elements are touched $\Theta(k)$ times, giving $\Theta(nk)$ overall.

Exam trick: Sequential (accumulator) merging is not $O(n\log k)$. The $\Theta(n\log k)$ bound is achieved only by balanced pairwise merging (a merge tree of depth $\log k$) or a min-heap $k$-way merge. Naive left-to-right merging repeatedly re-copies the growing prefix, so it degrades to $\Theta(nk)$.