Sorting Nearly Sorted Input

Problem

Sensor readings arrive over the network with timestamps, but because of independent buffering per sensor, a reading can appear up to k positions away from where it belongs in timestamp order. k is small (tens) and n is large (hundreds of millions). You must emit the readings in exact timestamp order.

1. Define the property precisely and explain why a general-purpose O(n log n) sort is doing unnecessary work.
2. Implement a sort whose cost depends on k rather than on n log n, working in a single streaming pass so you never hold the whole input.
3. Compare it with insertion sort and with the language's built-in sort on this input, and say which you would actually ship.

• Input: an iterable of comparable items with the guarantee that each item's final sorted index is within k of its current index.
• Output: a generator yielding items in sorted order.

Examples

• k = 0: the input is sorted; any sensible method should be O(n).
• Input [2, 1, 4, 3, 6, 5] with k = 1: every element is at most one position off. Output [1, 2, 3, 4, 5, 6].
• Input [3, 1, 2, 6, 4, 5] with k = 2: a window of size k + 1 = 3 always contains the next smallest element. Output [1, 2, 3, 4, 5, 6].
• n = 10⁸, k = 20: the heap method does n log(k + 1) ≈ 4.4 × 10⁸ comparisons; a general sort does n log n ≈ 2.7 × 10⁹; insertion sort does at most nk = 2 × 10⁹ shifts but O(n + inversions) in practice, and inversions are at most nk.

Hints

1. If every element is at most k positions from its home, where can the globally smallest element be?
2. What structure gives you the minimum of a small, changing set in O(log k)?
3. Insertion sort costs O(n + inversions). How many inversions can a k-sorted array have?