Sort a Nearly Sorted Array

Problem Statement

An array is nearly sorted (or K-sorted): each element is at most k positions away from where it would be in the fully-sorted array. Sort it efficiently — faster than a generic O(n log n) sort when k is small.

Input

An integer array arr that is K-sorted, and the window size k.

arr = [6, 5, 3, 2, 8, 10, 9]
k   = 3

Output

The fully sorted array.

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

Constraints

• 1 ≤ k < arr.length ≤ 10⁵
• Every element in arr is within k positions of its sorted location.

Intuition

Since an element can be at most K positions away, the smallest remaining element must be within the next k+1 positions. Seed a min-heap with the first k+1 elements. The root is guaranteed to be the smallest. Pop it (it’s done), push the next incoming element, repeat. We never look further ahead than k+1 elements — that’s the whole window we need.

seed window (first 4):   [6, 5, 3, 2]
heap (min):              [2, 5, 3, 6]
 
pop 2 → push 8   heap = [3, 5, 6, 8]    result = [2]
pop 3 → push 10  heap = [5, 8, 6, 10]   result = [2, 3]
pop 5 → push 9   heap = [6, 8, 9, 10]   result = [2, 3, 5]
drain:           pop 6, 8, 9, 10        result = [2, 3, 5, 6, 8, 9, 10] ✓

Solution

import heapq
 
def nearlySorted(arr: list[int], k: int) -> list[int]:
    h = arr[:k + 1]                      # seed with first k+1 elements
    heapq.heapify(h)                     # O(k)
    result: list[int] = []
 
    for i in range(k + 1, len(arr)):
        result.append(heapq.heappop(h))
        heapq.heappush(h, arr[i])
 
    while h:                              # drain the rest
        result.append(heapq.heappop(h))
    return result

function nearlySorted(arr: number[], k: number): number[] {
  const h = new Heap<number>((a, b) => a - b, arr.slice(0, k + 1));
  const out: number[] = [];
  for (let i = k + 1; i < arr.length; i++) {
    out.push(h.pop()!);
    h.push(arr[i]);
  }
  while (h.size > 0) out.push(h.pop()!);
  return out;
}

Complexity

Edge Case Thinking