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

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.