Sort a Nearly Sorted (K-Sorted) Array

You are given an array of n integers where every element is at most k positions away from where it would sit in the fully sorted array (a "k-sorted" or "nearly sorted" array). Sort the array so it is in non-decreasing order. An efficient solution should take advantage of the bound k rather than treating the array as arbitrarily unsorted.

Input: The first line contains two integers n and k. The second line contains n space-separated integers. Output: Print the n integers sorted in non-decreasing order, space-separated, on a single line.

1 <= n <= 8000 0 <= k < n -10^9 <= a[i] <= 10^9 Every element is guaranteed to be at most k positions away from its position in the fully sorted array

This is the SAME underlying technique as the identically-named Heap-category problem and the linked-list version of this exact idea - recognizing that a k-sorted guarantee, regardless of the underlying data structure (array, linked list), always suggests a size-(k+1) min-heap.

Sort an array where no element is more than k positions away from its correct sorted position, exploiting that bound for extra speed. Brute force: Sort the whole array with a general O(n log n) algorithm, ignoring the k-sorted guarantee entirely - this works but is slower than necessary when k is much smaller than n. Optimised: Since no value is more than k positions from its true sorted position, the TRUE minimum of the entire remaining array is GUARANTEED to already be among the first k+1 unprocessed values at any point - a min-heap of size just k+1 is always enough to correctly know the next output value, giving O(n log k) instead of the general O(n log n).

1. Push the first k+1 elements into a min-heap. 2. For each subsequent element in the array, pop the heap's minimum (that's guaranteed to be the next correctly-sorted output value) and push the new element in. 3. Once the whole array has been pushed, drain whatever remains in the heap - it comes out in sorted order.

Time: O(n log k) - each of the n elements triggers one O(log k) heap operation. Space: O(k), for the size-(k+1) min-heap.

k could be 0, meaning the array is already fully sorted; n could also be as small as 1.

Be ready to explain why a heap of exactly size k+1 (not k) is the precise bound needed - this follows directly from the problem's own 'at most k positions away' guarantee, and getting this off-by-one exactly right matters.