You are given a list nums that is nearly sorted: every element is at most k positions away from where it belongs in fully sorted order. Return the list in ascending order.
A full O(n log n) sort would work, but the guarantee lets you do better: aim for O(n log k).
Examples
Input: nums = [6, 5, 3, 2, 8, 10, 9], k = 3
Output: [2, 3, 5, 6, 8, 9, 10]
Explanation: 2 is at index 3 but belongs at index 0, a displacement of 3 = k.
Input: nums = [1, 2, 3], k = 0
Output: [1, 2, 3]
Constraints
0 <= len(nums) <= 10**5,0 <= k < len(nums)(ork = 0for an empty list)- Every element is guaranteed to be within
kpositions of its sorted position. - Target complexity: O(n log k).
Goals
- Exploit a bound on how far elements are displaced
- Keep a heap of bounded size while streaming through the input
- Emit elements in sorted order faster than a full sort