Sort a nearly sorted K sorted array
MediumUpdated: Aug 10, 2025
Problem
You are given a list of N numbers, in which each number is located at most k places away from its sorted position.
For example, if k = 3, a given element at index 4 might end up at any index between [1, 7]
indices: 0 1 2 3 4 5 6 7 8 9 10 11
^ ^ ^
<---------->
Come up with an algorithm that sorts this list in O(N log k) time.
Examples
Example 1
Input: nums = [6, 5, 3, 2, 8, 10, 9], k = 3
Output: [2, 3, 5, 6, 8, 9, 10]
Explanation: Each element is at most 3 positions away from its sorted position.
Example 2
Input: nums = [3, 2, 1, 5, 4, 7, 6, 5], k = 1
Output: [1, 2, 3, 4, 5, 5, 6, 7]
Explanation: Each element is at most 1 position away from its sorted position.
Example 3
Input: nums = [1, 4, 5, 2, 3, 7, 8, 6, 10, 9], k = 2
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Explanation: Each element is at most 2 positions away from its sorted position.
Solution
Solution
Method 1 - Brute Force Sorting
The simplest approach is to ignore the nearly sorted property and apply any standard sorting algorithm. However, this doesn't leverage the fact that elements are already close to their correct positions.
Complexity
- ⏰ Time complexity:
O(N log N), standard sorting without using k-sorted property - 🧺 Space complexity:
O(1)for in-place sorting algorithms
Method 2 - Insertion Sort
Intuition
Insertion sort performs well on nearly sorted arrays. Since each element is at most k positions away from its correct place, we can leverage this property to achieve better performance than general sorting.
Approach
- Use insertion sort which naturally handles nearly sorted arrays efficiently
- For each element, we only need to shift it at most k positions to the left
- Since elements are close to their correct positions, insertion sort becomes much faster
- Time complexity improves from O(N²) to O(N×k) due to limited displacement
Code
C++
class Solution {
public:
vector<int> sortArray(vector<int>& nums, int k) {
for (int i = 1; i < nums.size(); i++) {
int key = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
}
return nums;
}
};
Go
func sortArray(nums []int, k int) []int {
for i := 1; i < len(nums); i++ {
key := nums[i]
j := i - 1
for j >= 0 && nums[j] > key {
nums[j+1] = nums[j]
j--
}
nums[j+1] = key
}
return nums
}
Java
class Solution {
public int[] sortArray(int[] nums, int k) {
for (int i = 1; i < nums.length; i++) {
int key = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
}
return nums;
}
}
Python
class Solution:
def sortArray(self, nums: List[int], k: int) -> List[int]:
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
return nums
Complexity
- ⏰ Time complexity:
O(N×k), each element moves at most k positions, better than O(N²) - 🧺 Space complexity:
O(1), in-place sorting
Method 3 - Min Heap Approach
Intuition
Since each element is at most k positions away from its correct place, we can use a min heap of size k+1. The smallest element in the first k+1 elements must be the first element in the sorted array. We can continuously extract the minimum and add new elements to maintain this property.
Approach
- Create a min heap with the first k+1 elements
- Extract the minimum element (this is the next element in sorted order)
- Add the next element from the array to the heap
- Repeat until all elements are processed
- Extract remaining elements from the heap
Code
C++
class Solution {
public:
vector<int> sortArray(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
int n = nums.size();
vector<int> result;
// Add first k+1 elements to heap
for (int i = 0; i <= k && i < n; i++) {
minHeap.push(nums[i]);
}
// Process remaining elements
for (int i = k + 1; i < n; i++) {
result.push_back(minHeap.top());
minHeap.pop();
minHeap.push(nums[i]);
}
// Extract remaining elements
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
return result;
}
};
Go
import "container/heap"
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func sortArray(nums []int, k int) []int {
minHeap := &IntHeap{}
heap.Init(minHeap)
n := len(nums)
result := make([]int, 0, n)
// Add first k+1 elements to heap
for i := 0; i <= k && i < n; i++ {
heap.Push(minHeap, nums[i])
}
// Process remaining elements
for i := k + 1; i < n; i++ {
result = append(result, heap.Pop(minHeap).(int))
heap.Push(minHeap, nums[i])
}
// Extract remaining elements
for minHeap.Len() > 0 {
result = append(result, heap.Pop(minHeap).(int))
}
return result
}
Java
class Solution {
public int[] sortArray(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int n = nums.length;
int[] result = new int[n];
int resultIndex = 0;
// Add first k+1 elements to heap
for (int i = 0; i <= k && i < n; i++) {
minHeap.add(nums[i]);
}
// Process remaining elements
for (int i = k + 1; i < n; i++) {
result[resultIndex++] = minHeap.poll();
minHeap.add(nums[i]);
}
// Extract remaining elements
while (!minHeap.isEmpty()) {
result[resultIndex++] = minHeap.poll();
}
return result;
}
}
Python
class Solution:
def sortArray(self, nums: List[int], k: int) -> List[int]:
import heapq
min_heap = []
n = len(nums)
result = []
# Add first k+1 elements to heap
for i in range(min(k + 1, n)):
heapq.heappush(min_heap, nums[i])
# Process remaining elements
for i in range(k + 1, n):
result.append(heapq.heappop(min_heap))
heapq.heappush(min_heap, nums[i])
# Extract remaining elements
while min_heap:
result.append(heapq.heappop(min_heap))
return result
Complexity
- ⏰ Time complexity:
O(N log k), each of N elements involves heap operations of O(log k) - 🧺 Space complexity:
O(k), heap stores at most k+1 elements