Sort a Nearly Sorted (K-Sorted) Array

Problem Statement

An array is k-sorted if every element is at most k positions away from its final sorted position. Sort it efficiently using this guarantee.

Example

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

Approach

Maintain a min-heap of the next k + 1 elements. Because any element is within k of its place, the smallest of the current window is always the next element in sorted order. Pop it, push the next input element, and repeat.

Complexity

• Time: O(n log k)
• Space: O(k)

Solution Code

Python

import heapq
def sort_k_sorted(arr, k):
    heap = arr[:k + 1]
    heapq.heapify(heap)
    result = []
    for i in range(k + 1, len(arr)):
        result.append(heapq.heappushpop(heap, arr[i]))
    while heap:
        result.append(heapq.heappop(heap))
    return result

Java

int[] sortKSorted(int[] arr, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int[] res = new int[arr.length];
    int idx = 0;
    for (int i = 0; i < arr.length; i++) {
        heap.offer(arr[i]);
        if (heap.size() > k + 1) res[idx++] = heap.poll();
    }
    while (!heap.isEmpty()) res[idx++] = heap.poll();
    return res;
}

C++

vector<int> sortKSorted(vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;
    vector<int> res;
    for (int i = 0; i < (int)arr.size(); i++) {
        heap.push(arr[i]);
        if ((int)heap.size() > k + 1) { res.push_back(heap.top()); heap.pop(); }
    }
    while (!heap.empty()) { res.push_back(heap.top()); heap.pop(); }
    return res;
}

Key Takeaways

• A window heap of size k+1 exploits the "almost sorted" guarantee.
• O(n log k) beats a full O(n log n) sort when k is small.
• Reference: classic heap problem (GeeksforGeeks, "Sort a nearly sorted array").