Sort a Nearly Sorted List

Problem

A sensor log arrives almost in order: every reading is at most k positions away from the place it would occupy in the fully sorted log. Given the list and k, return the readings in ascending order. The answer should take O(n log k) time, which beats a general sort when k is much smaller than n.

Examples

Input:  nums = [3, 1, 2, 6, 4, 5], k = 2
Output: [1, 2, 3, 4, 5, 6]
Why:    3 sits two places early, 1 and 2 one place late

Input:  nums = [10, 9, 8, 7], k = 3
Output: [7, 8, 9, 10]
Why:    a reversed list of four values is still within 3 places

Input:  nums = [1, 2, 3], k = 0
Output: [1, 2, 3]
Why:    edge case, k = 0 means everything is already in place

Hints

0 / 3

1. Hint 1reveal
2. Hint 2locked
3. Hint 3locked

import heapq

def sort_nearly(nums, k):
    heap, out = [], []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:            # k + 1 candidates: the smallest is final
            out.append(heapq.heappop(heap))
    while heap:                      # input exhausted, drain in order
        out.append(heapq.heappop(heap))
    return out

print(sort_nearly([3, 1, 2, 6, 4, 5], 2))  # -> [1, 2, 3, 4, 5, 6]
print(sort_nearly([10, 9, 8, 7], 3))       # -> [7, 8, 9, 10]
print(sort_nearly([1, 2, 3], 0))           # -> [1, 2, 3]