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}.