Sort a K-Messed Array

If every element is at most k positions from its sorted location, the next output must be among the next k+1 unseen elements. Heapify the first k+1, then for each remaining element pop the minimum to output and push the new element. Drain at the end. The result is O(n log(k+1)) time and O(k) space, better than a full sort when k is small. A heap of only k elements can miss the next minimum. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.