Sort a K-Sorted (Nearly Sorted) Array

The problem. You're given an array nums that is nearly sorted: every value is at most k positions away from where it belongs in sorted order. Return the values sorted in ascending order — faster than an ordinary sort, by using the fact that nothing is far from home.

Example

nums = [6, 5, 3, 2, 8, 10, 9],  k = 3  ->  [2, 3, 5, 6, 8, 9, 10]
nums = [2, 1, 4, 3, 6, 5],      k = 1  ->  [1, 2, 3, 4, 5, 6]
nums = [1, 2, 3],               k = 0  ->  [1, 2, 3]      (already sorted)