Min Heap K Sorted Sort

Min heap k sorted sort is the canonical heap based method for sorting a k sorted array. It maintains a sliding window of size ( k + 1 ) in a min heap and repeatedly extracts the next smallest element.

This is the standard optimal solution for k sorted input.

Problem

Given an array ( A ) where each element is at most ( k ) positions away from its sorted position, produce the fully sorted array.

Idea

At position ( i ), the correct element must lie within the range:

[ [i, i + k] ]

So a min heap of size ( k + 1 ) always contains the correct candidate.

Algorithm

min_heap_k_sorted_sort(A, k):
    heap = min_heap()

    for i in 0..min(k, length(A)-1):
        heap.push(A[i])

    index = 0

    for i in k+1..length(A)-1:
        A[index] = heap.pop()
        index = index + 1
        heap.push(A[i])

    while heap not empty:
        A[index] = heap.pop()
        index = index + 1

    return A

Example

Input:

[ A = [2, 6, 3, 12, 56, 8] ]

with ( k = 3 )

Process:

• initial heap: [2, 6, 3, 12]
• output 2 → insert 56
• output 3 → insert 8
• output 6 → continue

Final result:

[ [2, 3, 6, 8, 12, 56] ]

Correctness

The invariant is:

• the heap contains all elements that could be the next output

Because each element is at most ( k ) positions away, no smaller unseen element exists outside the heap window. Extracting the minimum yields the correct next element.

Complexity

This improves over general sorting when ( k \ll n ).

Notes

This algorithm is effectively identical to the previous method but emphasizes:

• sliding window behavior
• strict ( k+1 ) heap size
• in-place overwrite of output

When to Use

Use this method when:

• the array is guaranteed k sorted
• you want predictable ( O(n \log k) ) performance
• memory usage must remain small

It is widely used in streaming merge scenarios and near-sorted data pipelines.