The Nearly Sorted Array: Sort with Minimum Swaps

In the restoration lab of Prime City, the Curator has a nearly sorted array ÔÇö each element is at most k positions away from its final sorted position. The Curator wants to sort the array efficiently using a min-heap of size k+1. "When each element is at most k positions from its target," the Curator explains, "we can use a sliding window min-heap of size k+1. Extract the minimum, place it in the output, and add the next element from the array. This sorts in O(n log k) time." Given an array of N integers where each element is at most k positions away from its target position, sort the array. Output the sorted array, space-separated. Constraints: 1 <= N <= 10^5, 1 <= k <= N, each element is at most k positions from its sorted position Input: 6 2 6 3 12 56 8 3 Output: 2 3 6 8 12 56 Input: 4 1 2 3 4 1 Output: 1 2 3 4