Sort a Nearly Sorted Array

1. Define the problem

You are given an integer array nums and an integer k, where every element is at most k positions away from where it would sit in the fully sorted array — a nearly sorted array. Sort nums in non-decreasing order. Because the array is only locally out of order, insertion sort only ever needs to shift a key back at most k positions, giving O(n·k) time — close to O(n) when k is small — instead of the full O(n²) worst case.

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ k ≤ nums.length
every value in nums is at most k positions from its position in the sorted array
-10⁴ ≤ nums_i ≤ 10⁴

Example

Inputnums = [3, 1, 2, 5, 4], k = 2

Output[1, 2, 3, 4, 5]

Explanation Every value is at most 2 positions from its sorted position, so each key shifts back at most 2 slots.

2. Know the words first

In plain terms

Nearly sorted: Every value sits within k positions of where it belongs in the fully sorted array — a small local shuffle, not a random shuffle.

3. Visualize the solution

Shift each key back at most k positions

Statusinit

k = 2. Key = 1 (index 1) may shift back at most 2 positions.

What happens in this step

nums = [3, 1, 2, 5, 4], k = 2
key = nums[1] = 1, window: indices >= i - k = -1 (i.e. back to index 0)

The window bound (i - k) caps how far left a key may look; for i=1 it still reaches all the way to index 0.

Step 1 of 5

Steps to visualize

Walk the array left to right, treating each value as a key.
Compare the key against the sorted prefix, but only look back up to k positions.
Shift bigger values within that window one slot right.
Drop the key into the gap once a smaller value is found or the window boundary is reached.
Because k bounds every shift, the whole sort finishes in O(n·k) time.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Shift each key back at most k positions

Statusinit

k = 2. Key = 1 (index 1) may shift back at most 2 positions.

What happens in this step

nums = [3, 1, 2, 5, 4], k = 2
key = nums[1] = 1, window: indices >= i - k = -1 (i.e. back to index 0)

The window bound (i - k) caps how far left a key may look; for i=1 it still reaches all the way to index 0.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function sortNearlySorted(nums, k) {
  for (let i = 1; i < nums.length; i++) {
    const key = nums[i];
    let j = i - 1;

    while (j >= 0 && j >= i - k && nums[j] > key) {
      nums[j + 1] = nums[j];
      j--;
    }

    nums[j + 1] = key;
  }

  return nums;
}

Time: O(n·k)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [3, 1, 2, 5, 4], k = 2`	`[1, 2, 3, 4, 5]`	example from the docstring
`nums = [1, 2, 3, 4], k = 0`	`[1, 2, 3, 4]`	k = 0 means no element is out of place at all
`nums = [2, 1, 4, 3], k = 1`	`[1, 2, 3, 4]`	k = 1, every value is one adjacent swap from sorted
`nums = [7], k = 0`	`[7]`	smallest valid input, a single element
`nums = [2, 2, 1, 3, 3], k = 2`	`[1, 2, 2, 3, 3]`	repeated values within the nearly sorted window
`nums = [-1, -3, -2, 0], k = 2`	`[-3, -2, -1, 0]`	negative values mixed with a positive value
`nums = [5, 3, 4, 1, 2], k = 4`	`[1, 2, 3, 4, 5]`	k large enough to behave like plain insertion sort

Sort a Nearly Sorted Array