Sort K-Sorted Arrays

Tags

Sort K-Sorted Arrays

Category

Heaps

Difficulty

Hard

Problem Statement

Given an array where each element is at most k positions away from its correctly sorted position (a "k-sorted" or "nearly sorted" array), sort the array efficiently. Formally, for each element at index i in the sorted output, it originally appears at some index j in the input where |i - j| <= k.

Intuition

Since each element is within k positions of its final location, we do not need a full sort. A min-heap of size k+1 is sufficient: at any point, the minimum of the next k+1 elements is guaranteed to be the next element in sorted order. We slide this window of size k+1 through the array, extracting the minimum and inserting the next element, producing the sorted output incrementally.

Approach

  1. Initialize a min-heap with the first min(k+1, n) elements of the array.
  2. Initialize an insertion index at 0.
  3. For each remaining element in the array: a. Extract the minimum from the heap and place it at the current insertion index. b. Insert the next element into the heap. c. Increment the insertion index.
  4. After all elements are processed, extract remaining elements from the heap and place them in order.
  5. Return the sorted array.

Pseudocode

function sortKSortedArray(array, k):
    minHeap = new MinHeap()
    n = length(array)

    // Insert first k+1 elements
    for i from 0 to min(k, n - 1):
        minHeap.insert(array[i])

    insertIdx = 0
    for i from k + 1 to n - 1:
        array[insertIdx] = minHeap.extractMin()
        minHeap.insert(array[i])
        insertIdx += 1

    while minHeap is not empty:
        array[insertIdx] = minHeap.extractMin()
        insertIdx += 1

    return array

Time & Space Complexity

  • Time: O(n log k), where n is the array length. Each of the n elements is inserted and extracted from a heap of size at most k+1. Each heap operation is O(log k).
  • Space: O(k) for the min-heap.

Key Insights

  • The heap size never exceeds k+1, which is what gives us the O(n log k) time complexity -- much better than O(n log n) for general sorting when k is small.
  • This is optimal for comparison-based sorting of k-sorted arrays.
  • When k = 0, the array is already sorted.
  • When k = n-1, this degrades to heap sort, which is O(n log n).
  • The approach works for any data stream where you know the "displacement bound" k.

Edge Cases

  • k = 0: array is already sorted, return as-is.
  • k >= n-1: the array could be in any order; the algorithm still works but with no advantage over general sorting.
  • Single element array: already sorted.
  • All elements are the same: already sorted.
  • k = 1: each element is at most one position away from its sorted position.

Linked mentions