K Sorted Array Sort

K sorted array sort handles a nearly sorted array where every element is at most ( k ) positions away from its final sorted position. This stronger assumption allows a heap based method faster than general sorting.

You use it when the disorder is locally bounded.

Problem

Given an array ( A ) of length ( n ), where each element is at most ( k ) positions away from its position in the fully sorted order, sort ( A ).

Idea

For the next output position, the correct element must be among the next ( k + 1 ) unread elements. Keep those candidates in a min heap, repeatedly extract the smallest, and insert the next unread item.

Algorithm

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

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

    write = 0

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

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

    return A

Example

Input:

[ A = [3, 1, 2, 6, 4, 5, 8, 7] ]

Here ( k = 2 ). Each element is at most two positions away from its final sorted position.

Sorted result:

[ [1, 2, 3, 4, 5, 6, 7, 8] ]

Correctness

At any output position ( i ), the element that belongs there cannot appear more than ( k ) positions later in the input. Therefore it is among the current heap candidates. Extracting the heap minimum writes the correct next element.

Repeating this argument for each position produces the full sorted order.

Complexity

When ( k ) is small, this is much faster than ( O(n \log n) ) sorting.

When to Use

Use K sorted array sort when:

• the input is almost sorted
• every item has bounded displacement
• ( k \ll n )
• stable ordering is not required

If the bound ( k ) is unknown or large, adaptive merge based sorting may be more suitable.