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

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?

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. The key property of selection sort here is that it has constant moves per block, so only #comparisons is square.

After this phase, for each element A[i] in the array there are at most k-1 elements "wrongly sorted" below it, that is elements at positions j<i such that A[j]>A[i]. These are (possibly) in the closest block below it that comes from the other merged part. Note that the first element of the block (and all other blocks below it) are already properly sorted relative to A[i] because of the blocks being sorted on their first elements. This is why the second phase works, i.e. achieves the fully sorted array:

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.

This is by no means a simple problem It is possible, but rarely done in practice because it's so much more complicated than a standard merge using N-scratch space. Huang and Langston's paper has been around since the late 80's, though practical implementations didn't really surface until later. Earlier, L. Trabb-Prado's paper in 1977 predates Huang and Langston significantly, but I'm challanged to find the exact text that paper; only references abound.

An excellent later publication, Asymptotically efficient in-place merging (1995) by Geert, Katajainenb, and Pasanen is a good coverage of multiple algorithms, and references Trabb-Prado's contributions to the subject.