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:
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:
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 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:
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.
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.,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
Also search for [insitu merge] in the bibliography. * A[i..j) = {A[i], ..., A[j-1]} if i<j, and is empty otherwise. |
|
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso-8859-1, fetched Thursday, 01-Jun-2023 06:11:57 UTC. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off. |