173. Sort a Nearly Sorted (K-Sorted) Array

An array of n integers is 'k-sorted': every element is at most k positions away from where it would be in the fully sorted array. Given such an array and k, produce the fully sorted array.

Input: The first line contains an integer n. The second line contains n space-separated integers forming a k-sorted array. The third line contains the integer k. Output: Print the fully sorted array, space-separated.

0 <= k < n <= 10^5

This is a great illustration of exploiting a problem's SPECIFIC extra guarantee (bounded disorder) to beat the general O(n log n) sorting lower bound that would apply to a completely arbitrary, unbounded array.

Sort an array where every element is guaranteed to be at most k positions away from its correct sorted position. Brute force: Sort the whole array with a general-purpose sort - this costs O(n log n), correct but doesn't exploit the guarantee that disorder is bounded by k, which allows a faster approach when k is much smaller than n. Optimised: Since every element is guaranteed to be within k positions of its true sorted position, the true minimum of the whole remaining array is ALWAYS within the next k+1 elements seen so far - a heap of just size k+1 (not the whole array) is sufficient to always correctly extract the next sorted element.

Because every element is at most k positions from its sorted position, an insertion sort only ever needs to shift an element back by at most k slots to place it correctly, instead of potentially all the way to the start. Walking through the array and inserting each element into its correct spot among the previous k+1 elements exploits the k-sorted guarantee directly, giving a real speed-up over generic sorting whenever k is small relative to n, while using no extra memory. Time: O(n*k) Space: O(1)

Simply run a standard comparison-based sort (e.g. merge sort or the language's built-in sort) on the whole array, completely ignoring the fact that it is k-sorted. This is correct because any correct general sort produces the fully sorted array regardless of the input's structure, but it wastes the guarantee that no element needs to move more than k positions, so it can't do better than the generic sort bound no matter how small k is. Time: O(n log n) Space: O(n)

Push the first k+1 elements into a min-heap. Then, for each subsequent element, pop the minimum from the heap (it is guaranteed to be the next smallest value overall, since no smaller value can appear more than k positions later) and push the new element in. Once the array is exhausted, drain the remaining heap. This guarantees correctness from the same displacement bound as insertion sort but replaces the O(k) linear shifting with O(log k) heap operations, making it the fastest option when k is much smaller than n. Time: O(n log k) Space: O(k)

1. Maintain a min-heap containing the next k+1 elements from the array - the TRUE minimum of the entire remaining array is guaranteed to be somewhere within this small window. 2. Repeatedly extract the heap's minimum (it's provably the correct next element in sorted order), output it, and insert the next unseen element from the array to replace it. 3. Continue until the array is exhausted, then empty out the remaining heap in sorted order.

Time: O(n log k) - each of the n elements triggers one push and one pop on a heap of size k+1. Space: O(k), for the heap.

k = 0 (the array is already sorted), k = n-1 (the maximum allowed displacement), and n = 10^5 for heap-window performance.

Be ready to explain WHY a window of exactly k+1 (not k, and not some other size) guarantees correctness - this precise bound directly follows from the problem's own 'at most k positions away' guarantee.