Outline of the algorithm to merge one pair of runs of length len=2 ^k-1 into one run of length 2 ^k –

Note: Whenever I first recognized the need for another function argument I put the argument in brackets [ ]. Also, phrases in braces { }represent details to be handled later.

set runs_done flag to false (Set to true only when both current runs have been processed)

get next item from [input_stream_1] and store in current_item_1 {gets first item of new run}

get next item from [input_stream_2] and store in current_item_2

set count_1 and count_2 to 0. (counters are used to track number of items from each of the two current runs that have been processed)

while (not runs_done – in other words, as long as there is more data to process)
        if (current_item_1 < current_item_2)
            write current_item_1 to the [output_stream]
            increment count_1 (add one to this counter)
            if {there is any more data left in the current run in input_stream_1}
                get next item from [input_stream_1] and store in current_item_1
            else
                copy remaining items in input_stream_2 to output_stream
                set runs_done flag to true
            end of inner IF
        else
            write current_item_2 to the [output_stream]
            increment count_2 (add one to this counter)
            if {there is any more data left in the current run in input_stream_2}
                get next item from [input_stream_2] and store in current_item_2
            else
                copy remaining items in input_stream_1 to output_stream
                set runs_done flag to true
            end of inner if
        end of outer if
end of while loop