Merge two sorted quote streams

Question

Two feeds each deliver quote prices already sorted ascending. Merge them into a single sorted array without re-sorting from scratch. Return the merged sorted array. Aim for O(m + n).

Accepted Answer

Walk a pointer through each array. At each step, append the smaller of the two current heads and advance that pointer. When one array is exhausted, append whatever remains of the other, it is already sorted and all larger than everything emitted so far. Tracing a = [1, 4, 7], b = [2, 3, 8]: the merge emits 1 (from a), then 2, 3 (from b), then 4, 7 (from a), then 8 (from b), giving [1, 2, 3, 4, 7, 8]. Time O(m + n), space O(m + n) for the output. Using <= rather than < keeps the merge stable, equal elements from a come before those from b, which matters when the values carry attached data. Tak…

Merge two sorted quote streams

Your answer

More Coding questions