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

Decompose the $k$-sorted array into $k$ sorted chains.

The condition $A[i-k]\le A[i]\le A[i+k]$ links every element to the one $k$ positions before and after it. Group the indices by residue $r \bmod k$:

$\text{chain}_r = \big(A[r],\, A[r+k],\, A[r+2k],\, \dots\big),\quad r = 0,1,\dots,k-1.$

Within one chain, consecutive elements are exactly the pairs $A[i]$ and $A[i+k]$, and the hypothesis gives $A[i]\le A[i+k]$. Hence each of the $k$ chains is already individually sorted, and each has about $\tfrac{n}{k}$ elements.

Reduce to merging $k$ sorted lists.

Producing a fully ($1$-)sorted array is therefore exactly the problem of merging $k$ sorted lists whose total length is $n$. Using a min-heap of size $k$ (always holding the current head of each chain):

• each of the $n$ output elements is extracted with one $\texttt{extract-min}$ and one $\texttt{insert}$,
• every heap operation on $k$ items costs $O(\log k)$.

$T(n) = n \cdot O(\log k) = O(n\log k).$

Why the other options fail.

The matching lower bound $\Omega(n\log k)$ (each comparison sort decision tree must distinguish all interleavings of $k$ sorted lists) makes $\Theta(n\log k)$ optimal, so option 4 is the fastest.

Exam trick: A "$k$-sorted" array is just $k$ presorted subsequences in disguise. Recognize it as a $k$-way merge and the answer is always $O(n\log k)$, the same cost as merging $k$ sorted lists of total size $n$ with a min-heap.