Sort a nearly-sorted tick stream

Question

Timestamps arrive almost in order: each is at most k positions away from where it belongs in the fully sorted stream (network jitter shuffles nearby ticks). Sort the stream efficiently, exploiting the small displacement.

stream = [2, 1, 3, 4], k = 1
-> [1, 2, 3, 4]

Return the sorted stream. Aim for $O(n \log k)$ time and $O(k)$ space.

Accepted Answer

Because each element is within k of its final spot, the true minimum of the remaining stream is always among the next k + 1 elements. Keep a min-heap of size k + 1: seed it with the first k + 1 elements, then for each further element, pop the smallest (it is finalized) and push the newcomer. Drain the heap at the end. Tracing [2, 1, 3, 4] with k = 1: the heap starts as {1, 2}; pushing 3 pops 1, pushing 4 pops 2, then draining yields 3, 4. Output [1, 2, 3, 4]. Time O(n \log k), each of n elements touches a heap of size k + 1, and space O(k). This beats a full O(n \log n) sort when k is small, …

Sort a nearly-sorted tick stream

Your answer

More Coding questions