In-situ Merge

LA home
Computing
Algorithms
 glossary
 Sorting
  Insertion
  Quick
  Merge
  Heap
  Dutch N.F.
  Radix
  In-situ

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.
These operations take time that is linear in the number of elements moved.

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 seg1 and/or seg2:

seg1(sorted) seg2(sorted)
... large1 ... large2

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

largest seg1(sorted) seg2(sorted)
large1 & large2 ... ...

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

largest seg1(sorted) seg2(sorted)
block1 block2block3 ... blockiblocki+1 ...

Consider the blocks after block1. Using (a variation on) selection sort, rearrange these blocks so that their last elements are monotonic. This takes O((√N)2) 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 series1 and series2: Series1 starts with block2. Series2 is the first block (only) whose first element is smaller than the last element of the previous block, for example:

largest ↓series1 ↓series2  
block1 block2block3 block4block5 ...

Note that the last element of series2 is at least as large as the last element of series1 because of the earlier rearrangement of blocks.

Using block1 as (moving) workspace, merge series1 and series2 into the start of A, favouring series1 when breaking ties. Continue until all elements of series1 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 series1 and series2.

merged   ↓series1 ↓series2  
...sorted... largest part block4block5 block6 block7 ...

The new series1 starts with the first unmoved element of the old series2. The new series2 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)2)-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 seg1 and/or seg2 – 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 seg1 and/or seg2 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(k2)-time.

E.g.,

seg1:
seg1:
A[ ]:
N:

output:

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.

www:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Wednesday, 05-Aug-2020 21:26:32 EDT.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.