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?
6 Answers
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.
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.
Related