In-situ Merge

Given an array of N elements, A[0..N)^*, such that segment A[0..N1) is sorted and segment A[N1..N) is sorted, where 0 ≤ N1 ≤ N, rearrange A[0..N) so that it is sorted. Merging lies at the heart of the merge-sort algorithm (where initially A[p..q) and A[q..r) are sorted, 0 ≤ p ≤ q ≤ r ≤ N, and A[p..r) must be made sorted).

The obvious ways to do the merge use extra workspace. For example, copy A[0..N1) into workspace W[0..N1), and set pointers p1 to zero, p2 to N1 and p to zero. Then repeatedly copy the smaller of W[p1] and A[p2] to A[p] advancing p and either p1 or p2 as appropriate; when of the segments is exhausted copy over the remainder of the other one. The obvious methods take linear-time but use up to O(N) extra workspace.

It turns out that it is possible to do the merge in-situ, that is using only a constant amount of extra workspace, and still in linear-time. Such algorithms involve considering A[0..N1) and A[N1..N) to be made up of consecutive blocks of size √N. The algorithms are easiest to understand when N1 and (N-N1) are multiples of √N but they can be made to work when this is not the case. There are even stable versions of the algorithms although the degree of difficulty is much higher.

Some basic operations are used by the various merge algorithms:

swap_N(A, lo1, lo2, N)

exchange the contents of A[lo1..lo1+N) and A[lo2..lo2+N)
e.g., swap A[lo1] and A[lo2]; swap A[lo1+1] and A[lo2+1]; ... etc

swapSegs(A, p, q, r)

exchange the adjacent segments A[p..q) and A[q..r)
e.g., reverse A[p..q); reverse A[q..r); reverse A[p..r), will do although
there are better methods.

Huang and Langston, unstable algorithm (1988):

For simplicity and for now, assume that N is a perfect square. The √N largest elements in A[] must be at the end of seg₁ and/or seg₂:

Using swapSegs operations, move the √N largest to the front of the array (in any order):

Assume, for now, that the two remaining sorted segments each consist of whole blocks of size √N:

Consider the blocks after block₁. Using (a variation on) selection sort, rearrange these blocks so that their last elements are monotonic. This takes O((√N)²) comparisons of last elements and O(√N) moves of blocks of size O(√N) so it can be done in O(N)-time.

Next find series₁ and series₂: Series₁ starts with block₂. Series₂ is the first block (only) whose first element is smaller than the last element of the previous block, for example:

Note that the last element of series₂ is at least as large as the last element of series₁ because of the earlier rearrangement of blocks.

Using block₁ as (moving) workspace, merge series₁ and series₂ into the start of A, favouring series₁ when breaking ties. Continue until all elements of series₁ have been correctly placed. Note that the first part of the array is now sorted and the largest elements have migrated to immediately follow this sorted part. Now find a new series₁ and series₂.

The new series₁ starts with the first unmoved element of the old series₂. The new series₂ is found as before. Repeat until the series are empty.

Eventually most of the array is sorted and the largest elements have migrated to the right hand end of the array. The only problem is that the relative order of the largest elements may have been scrambled but there are only √N of them: Sort them, in O((√N)²)-time, i.e., in O(N)-time. Done.

Of course the initial assumptions may not hold: N may not be a perfect square and, even if it is, the segments may not consist of whole blocks of size √N. If N is not a perfect square, let b = ⌊√N⌋, and N' = N - (N mod b). Find the N - N' largest elements of the array – these must be at the end of seg₁ and/or seg₂ – use a swap to move them to the right hand end of the array and sort them (in at worst O(N)-time) then work on A[0..N').

Even if N is a perfect square or has been made multiple of a block size that is approximately √N, the lengths of the two segments may not be multiples of the block size. If so, find the largest elements at the end of seg₁ and/or seg₂ such that swapping positions will result in two (sorted) segments with lengths that are both multiples of the block size. Proceed as before.

As a practical matter, if the array has fewer than some small fixed number of elements, k, do not apply the algorithm above, just sort it in O(k²)-time.

E.g.,

Is in-situ merge of any practical use? After all, modern computers have enormous memory and even larger virtual memory. Well maybe, because although in-situ merge has a worse constant of proportionality in its time-complexity, it has better locality – about half the working-set – of other merges: Think about (multi-level) caches.

— L.A. 29 September 2018

References

M. A. Kronrod, An optimal ordering algorithm without a field of operation, Dokl. Akad. Nauk USSR, 186(6), pp.1256-1258, 1969

dan34705@[mathnet.ru]['18].

H. Mannila & E. Ukkonen, A simple linear-time algorithm for in-situ merging, Inf. Proc. Lett., 18(4), pp.203-208, 1984

doi:10.1016/0020-0190(84)90112-1

B.-C. Huang & M. A. Langston, Practical in-place merging, Comm. of the ACM, 31(3), pp.348-352, 1988

doi:10.1145/42392.42403, also pdf@[www]['18].

B.-C. Huang & M. A. Langston, Fast stable merging and sorting in constant extra space, The Computer Jrnl, 35(6), pp.643-650, 1992

doi:10.1093/comjnl/35.6.643, also pdf@[www]['18].

Also search for [insitu merge] in the bibliography.

^* A[i..j) = {A[i], ..., A[j-1]} if i<j, and is empty otherwise.