Sort a k-sorted array, where each element is at most k positions from its final place

The signal is recognizing that 'each element is at most k away' bounds the window you ever need in memory, so a size-(k+1) heap suffices and a full O(n log n) sort is wasted work. The off-by-one on heap size is the thing that trips people: it must be k+1, not k, because the true next-smallest could be exactly k positions ahead. The streaming framing is the reserved follow-up, since the heap solution needs only k+1 elements buffered at any time.