Sort a K-Sorted Array

You are given an array arr of n integers and an integer k. Each element of arr is guaranteed to be at most k positions away from where it would sit in the fully sorted version of the array (this is sometimes called a "k-sorted" or "nearly sorted" array).

Sort the array. A general-purpose O(n log n) sort works, but you should give an approach that takes advantage of the k-sorted guarantee to do better when k is small.

Example 1

Input: arr = [3, 1, 2, 5, 4, 7, 6, 8], k = 2
Output: [1, 2, 3, 4, 5, 6, 7, 8]
Explanation: Every element is at most 2 positions from its final
sorted index.

Example 2

Input: arr = [1, 2, 3], k = 0
Output: [1, 2, 3]
Explanation: k = 0 means the array is already sorted.

Constraints

• 1 <= arr.length <= 10^5
• 0 <= k <= arr.length - 1
• -10^9 <= arr[i] <= 10^9
• Every element is guaranteed to be at most k positions from its final sorted position.