Pattern visualizer
Sort a K Sorted Array
The k-sorted promise is the whole algorithm: if a value belongs at position w, it cannot currently sit further right than w + k. Turn that around and the value that belongs at position w must already be among the first k+1 unplaced values — everything beyond them is too far right to reach position w. So keep exactly k+1 values in a min-heap, pop the root to fill the next answer slot, and read one fresh value in to refill the window. The heap never grows past k+1, so each of the n values costs log k instead of log n. Animated on: nums = [5,3,2,8,6,10,9], k = 2 — every value is at most 2 positions from its sorted place. Sort it without paying for a full O(n log n) sort..
Min-heap of size k+1 — a sliding window of candidates
nums=[5,3,2,8,6,10,9] is already nearly sorted: every value sits at most k=2 places from where it belongs. A full sort would pay O(n log n) and ignore that promise. Instead watch only a window of k+1=3 values — the true smallest can never be hiding further right than that.
1FUNCTION sortKSorted(nums, k):2 heap <- empty MIN-HEAP3 out <- empty list4 FOR i <- 0 TO k:5 PUSH nums[i] INTO heap6 FOR i <- k + 1 TO LENGTH(nums) - 1:7 APPEND POP-MIN(heap) TO out8 PUSH nums[i] INTO heap9 WHILE heap NOT EMPTY:10 APPEND POP-MIN(heap) TO out11 RETURN out
← / → step · space play · Home restart