Sort a nearly sorted array (each element at most k positions away)?

public int[] SortNearlySorted(int[] nums, int k) {
var result = new List<int>();
var minHeap = new SortedSet<(int val, int index)>();
for (int i = 0; i < nums.Length; i++) {

minHeap.Add((nums[i], i));

if (minHeap.Count > k) {
var min = minHeap.Min;

minHeap.Remove(min);

result.Add(min.val);

}
}

while (minHeap.Count > 0) {

var min = minHeap.Min;

minHeap.Remove(min);

result.Add(min.val);

}
return result.ToArray();
}

Explanation:

Use a min-heap of size k+1 to always extract the smallest element in the current window.