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.