This is both off-topic, and about as airey-fairey a question as I've ever asked.

You have two (equal length, though that may be irrelevant), sorted buffers of data, call them numbers for simplicity, and you have to merge them. In-place; though a small (say 10%) extra buffer could be used if it would help.

For reasons nothing to do with the merge, before performing it, you have to make (individually) a sequential pass of both buffers. Why, irrelevant to this question.

Is there anything that you could do during that pass, that would some how inform you in a way that would make the subsequent merge more efficient?

For example: although the passes over the two buffers only need to be done individually for their own requirement; is there anything that could be learned by running those passes in lock-step?

Ie. instead of: for i ( 0 .. n ) f( a[i] ); for i ( 0 .. n ) f'( b[i] ); we might do:

for i ( 0 .. n ) {
    f( a[i] );  // the required stuff for a[]
    f'( b[i] );  // the required stuff for b[]
    g( a[i], b[i] ); // and whilst we have them, do something to, or a
+ccumulate some statistic, that might help the subsequent merge.
}
[download]

Alternatively, there would be negligible cost and might be some benefit in doing:

f( a[0] ); f'( b[0] );
for i ( 1 .. n ) {
    f( a[i] );
    f'( a[i] );
    g( a[i], a[i-1] );
    g'( b[i], b[i-1] );
}
[download]

I know it is a nebulous question, so please don't bother telling me that; but, if just reading it triggers some idea; no matter how incomplete, please do.