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 routines

There is some notation and some operations that it is convenient to define for later use:

arr[i..j) stands for a[i], ..., a[j-1].

|arr[i..j)| = j-i.

swap_ij(i, j):

temp=arr[i]; arr[i]=arr[j]; arr[j]=temp;  also known as arr[i]:=:arr[j]

swap_ijk(i, j, k):

arr[i..j) :=: arr[j..k)
one method [MU84] is reverse arr[i..j); reverse arr[j..k); reverse arr[i..k); but we can do better [click].

swap_nij(n, i, j):

arr[i..i+n) :=: arr[j..j+n)

sort(i, j):

sort arr[i..j)
A simple quadratic-time sorting algorithm is good enough because we only sort two parts of arr each of size O(√N), although we might use a faster sort for the sake of honour (maybe heap-sort but not quick-sort because that would use more than O(1)-space).

smallMerge(i, j, k, ws):

merge sorted blocks arr[i..j) and arr[j..k) using workspace arr[ws..ws+j-i)
The contents of the workspace must be preserved but may be permuted. The solution is firstly to swap the contents of arr[i..j) with the contents of the workspace, and then to merge workspace and arr[j..k) into arr[i..k) swapping an element of arr[i..k) with one from the workspace when the latter is chosen.

nextBblock(j):

return the first k>B s.t. arr[k]>arr[j] or 'N' if there is no such k. If j is the end of the current A-block A_t, arr[B..nextBblock(j)) is B_t, the B-block that is to be merged with A_t.