*Bounty: 50*

*Bounty: 50*

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)$

time.

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 `result`

list:

```
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?