I first explained the brute-force approach using sorting (O(n log n)). Then I discussed the optimal solution using a min-heap. If each element is at most k positions away from its correct position, maintain a min-heap of size k+1 to sort the array in O(n log k) time and O(k) space. I also discussed the edge case where k is unknown, in which case a comparison sort is required in the general case.