Sort a K-Sorted Array

Medium

Given a k-sorted array, which is an array where each element is at most k positions away from its sorted position, sort the array.

1Example 1

Input:

{
  "arr": [
    6,
    5,
    3,
    2,
    8,
    10,
    9
  ],
  "k": 3
}

Output:

[
  2,
  3,
  5,
  6,
  8,
  9,
  10
]

2Example 2

Input:

{
  "arr": [
    10,
    9,
    8,
    7,
    4,
    70,
    60,
    50
  ],
  "k": 4
}

Output:

3Example 3

Input:

{
  "arr": [
    2,
    1
  ],
  "k": 1
}

Output:

[
  1,
  2
]