how to merge two sorted integer array in place using O(n) time and O(1) space cost

Question

For example, given an integer array and its two consecutive sequence 's beginning position which are 'b1' and 'b2', furthermore provided with the position 'last' which indicates the second sequence's ending position. From array[b1] to array [b2-1] and from array [b2] to array[last] are both in order separately, how to merge them in place using O(n) time and O(1) space cost?

Answer 1

This is by no means a simple problem; people are still writing research papers on the subject (PDF). It is possible, but rarely done in practice because it's so much more complicated than a standard merge using scratch space.

Answer 2

There are such things as true in-place merges, but they are not straightforward enough that anybody is going to independently reinvent them in the middle of an interview - there have been papers describing a succession of pretty complex algorithms for this for years. One is Practical In-Place Merging, by Huang and Langston, CACM March 1988. The starting idea for this is to divide the data of length n into blocks of size sqrt(n), and use one block, filled with the largest elements of the data, to provide buffer space used in merging the others. The introduction to that paper says

"Given two sorted lists whose lengths sum to n, the obvious methods for merging in O(n) steps require a linear amount of extra memory as well. On the other hand, it is easy to merge in place using only a constant amount of additional space by heap-sorting, but at a cost of O(n log n) time"

Hence I claim that true merging in place can be done but is non-obvious.

Answer 3

Kronrod's merge was the first published algorithm to do that. It goes roughly like this:

Split both parts of the array into blocks of size k=sqrt(n). Sort the blocks using their first elements as the basis for comparison. This can be done in sqrt(n)^2=O(n) by selection sort. Now merge the first block with the second, then second with the third, etc., using the last 2 blocks as temporary space for the output of the merge. This will scramble the contents of the last two blocks but in the last phase they (together with the preceding block) can be sorted by selection sort in sqrt(n)^2=O(n) time.