AlgoViz
HomeHeap / Priority Queue

Sort K sorted array

Easy

A heap of size k+1 is all you need

Problem

Sort a nearly-sorted array where each element is at most k positions from its sorted spot.

In simple words

Keep a min-heap of the next k+1 elements; popping the smallest each time sorts it fast.

The idea

Each element is at most k positions from its sorted place, so the true next element is always within the next k+1 candidates. Holding that window in a min-heap and extracting one at a time sorts the array in O(n log k).

The trick

  • Heap size k+1, never the whole array.
  • Extract the minimum after each insertion once the heap is full.
  • O(n log k), a real win over O(n log n) for small k.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

6
5
3
2
8
10
9
0
1
2
3
4
5
6

Step 1 of 2. Here's the example — [6,5,3,2,8,10,9], k=3 Values: 6, 5, 3, 2, 8, 10, 9.

1/2
Optimal
timeO(n log k)spaceO(k)
1min-heap of first k+1 elements2for each next element: pop min into output; push next

Input

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

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

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 spots from home.

Example 2

Input:
nums = [2, 1, 3], k = 1
Output:
[1, 2, 3]
Explanation:
A small heap fixes near-sorted data.

Example 3

Input:
nums = [1], k = 0
Output:
[1]
Explanation:
Already sorted.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.