I’m currently looking into the quickest way to sort an almost sorted array:
Given an array of $n$ elements, where each element is at most $k$ away
from its target position, devise an algorithm that sorts in $O(n log k)$
I’ve implemented a sorting function which “slides” through an input list, pushes the element from a sliding window into a min heap (using the
heapq built-in module), pops the minimum element which is collected in the
from typing import List from heapq import heappush, heappop def sort_almost_sorted(a: List[int], k: int) -> List[int]: if not a: return  length = len(a) if k >= length: return sorted(a) # apply built-in "timsort", designed to be quick on almost sorted lists result =  min_heap =  # maintain a min heap for a sliding window for slice_start in range(0, length, k + 1): # sliding window # push the next slice to min heap for index in range(slice_start, min(slice_start + k + 1, length)): heappush(min_heap, a[index]) result.append(heappop(min_heap)) # put the rest of the heap into the result for _ in range(len(min_heap)): result.append(heappop(min_heap)) return result
It works on my sample inputs.
Do you think I’m using the minimum heap appropriately and this implementation is $O(n log k)$? What would you improve code-quality or code-organization wise?