In-situ Merge |
|
The problem, given array arr[0..N) where section A, arr[0..B), is sorted and section B, arr[B..N), is sorted, is to rearrange the contents of arr[0..N) so that arr[0..N) is sorted and to do so efficiently, i.e., in O(N)-time using only O(1)-space. ...sec.A:sorted...|...sec.B:sorted... B N -- state of arr[0..N) at time t=0 -- The following description and implementation of a solution are based on the paper of Mannila and Ukkonen [MU84]. The aim is to give the simplest description and the simplest implementation running in linear-time and using O(1)-space; the reader may spot some places where optimisations are possible to reduce the "constant factor". Plainly the problem cannot be solved in less than linear time in general because it may be necessary to move every element of the array. 1. Some useful routinesThere is some notation and some operations that it is convenient to define for later use:
2. General StrategyIf the array is "small" say less 16 elements just sort it using any passable sort algorithm. Otherwise, if section A is small say less than eight elements, copy section A from arr into a new (bounded) workspace and merge section B and the workspace back into arr. Otherwise, the approach [MU84] is to merge blocks from A with blocks from B. The A-blocks are all of size ABS=⌊√|A|⌋, except possibly the first one A0 which has ABS+(|A| mod ABS) elements. Note that there must be at least three A-blocks and that the first is less than twice the size of the other A-blocks. The B-blocks, see nextBblock(.), can be of various sizes possibly from zero to |B| elements. As the algorithm progresses, arr[0..N) is in three sections; the first section grows and the other two sections shrink. The first section is done with, except that its first ABS elements can be used as workspace and their contents may be permuted. The second section, C, contains the remaining A-blocks but although each individual A-block is sorted, collectively they can be (i) out of order and (ii) frame-shifted so that the first block can be split. The third section is what remains of section B. ..done..|..sec.C..|..sec.B.. C B N -- state at time t≥1 -- 3. Getting StartedThe first A-block A0 may be larger than the others. It is conveniently in the right place. The corresponding B-block, B0 is found – see nextBblock(.). Swap B0 with the rest of C to bring B0 adjacent to A0. --A0-- -B0- |aaaaaaxxxxxxxx|bbbbyyyyyyyyyy C B N aaaaaabbbb|xxxxxxxx|yyyyyyyyyy ---------- C B N Advance C and B. Now use smallMerge(...) to merge A0 and B0 using the start of C, which must be big enough, as workspace and finally sort the workspace (it's size is <2×ABS). 4. IterationsThe remaining A-blocks are all of size ABS and each one is sorted, but they can be collectively out of order and frame-shifted within C so At has to be looked for and found. Mannila and Ukkonen suggest that
The A-blocks start at positions of the form C+(((j−1)×ABS−frameShift)mod (B−C)) and end at positions of the form C+j×ABS−1−frameShift, for j≥1. The next A-block, At, can be found by looking for the block with the smallest start- or(!) end-value (that is enough, e.g., consider C = '3,4,5,6; 2,2,2,2; 1,1,2,2; 2,2,3,3'). At is brought to the front of C. If At is split because of frame-shifting its head (at the end of C) is swapped with the elements next to its tail (at the start of C). The two parts of At are then swapped, making it sorted. ....|AAApqrstuvaa|... --- -- ....|AAApqrstuvaa|... >> << ....|AAAaarstuvpq|... >>><< ....|aaAAArstuvpq|... Otherwise At is not the first block in C. If At is the second block in C and the first block is not split then swap them. If the first block is split, swap its tail with the tail of At and then swap the two parts of At. ....|tuvaaAAApqrs|... >>> <<< ....|AAAaatuvpqrs|... >>><< ....|aaAAAtuvpqrs|... If At is neither of the first two blocks in C swap it with the second block and then proceed as before. When At is at the start of C, locate the corresponding B-block Bt. If Bt is no longer than the rest of C, swap Bt with part of C to bring Bt adjacent to At; this will change the frame-shift unless |Bt| is a multiple of ABS. If Bt is longer than the rest of C swap all of the latter with Bt. When At and Bt are adjacent smallMerge them using the first ABS elements of the array, arr[0..ABS), as workspace. The process is repeated until C becomes empty at which point the first ABS elements of the arr, which have been used for workspace, must be sorted and we are done. 5. Time and SpaceIt can be seen that, other than the given array, the algorithm [MU84] uses a few scalar variables, and a small bounded workspace in the case that section A of the array is small, i.e., it uses O(1)-space. Locating the next A-block is performed O(√|A|) times and each requires O(√|A|) comparisons, O(|A|)-time in total. Two blocks of size O(√|A|) are sorted but even if a slow quadratic sort is used this takes O(|A|)-time. Apart from that, each element of the given array is moved at most a fixed number of times so the algorithm runs in O(N)-time, i.e., linear time. 6. SummaryThe in-situ merge problem restricted to O(1)-space and O(N)-time is highly constrained and solutions are tricky with algorithmic steps being chosen like moves in a chess puzzle. Are solutions to this problem of any practical use (e.g., in merge-sort) compared to the well-known O(N)-space and -time merges given that modern computers have huge memories? It is hard to say but just maybe when you consider multi-level memory caches and working-set size. — L.A. 2/10/2023
7. References
|
|
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso-8859-1, fetched Sunday, 03-Dec-2023 08:17:23 UTC. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off. |