Sort a nearly sorted array

An integer array nums of size n is called k-nearly sorted if, after arranging its values in nondecreasing order, no element has moved more than k index positions from its original location. Equivalently, for each original index i, the value nums[i] belongs at some sorted index j with $$ i - j \le k$$. You are given such an array nums and the integer k. Return the fully sorted array in nondecreasing order. Design an algorithm that exploits the bounded-displacement guarantee.…