Order a Nearly Sorted UDP Packet Stream

A stream delivers integer UDP packet sequence numbers one after another. For every received item, its position in the incoming stream differs from its position in the fully sorted stream by no more than k positions. Implement sort_nearly_sorted(stream, k), which must return all received numbers in ascending order. The stream may be too large to fit in memory, so storing the entire stream is not allowed; your solution must use only $$O(k)$$ auxiliary space. Example 1:…