Remove x last elements of an array and reinsert them before position y

I am looking for an algorithm to move a subarray in before an element (which is not part of that subarray) in the same array where the last element of the subarray is the last element of the array with O(1) extra space and O(n) runtime.

e.g. where *p1 = 5 and *p2 = 3:

1 2 5 6 7 3 4

becomes

1 2 3 4 5 6 7

This is what I have so far (written in C programming language). Trouble arises when p1 reaches p2.

void swap(long* p1, long* p2, long* array_end) {
long* p2_i = p2;
while (p1 < array_end) {
if (p2_i > array_end) {
p2_i = p2;
}

// swap *p1 and *p2_i
long* temp = p1;
*p1 = *p2_i;
*p2_i = temp;

++p1;
++p2_i;
}
}

• What is your question? – orlp Oct 13 '19 at 15:48
• @orlp How do I make my algorithm work correctly? Fitting the requirements above. – Martin Oct 13 '19 at 16:13
• Make sketches - should it work? Think how you would describe the algorithm. Have a search engine turn up hits. There is one technique popular for at least half a century that has what you seem to be trying as one step. If you get stuck, describe your approach here (pseudo-code welcome, source code not really). – greybeard Oct 13 '19 at 16:34
• @greybeard What is the name of that technique? – Martin Oct 13 '19 at 17:25
• What is your description of a promising technique using that step? What did you come across searching for a prior description, a name? Its merits include cuteness and cache friendliness. – greybeard Oct 13 '19 at 20:16

We can assume without loss of generality that $$y$$ is the first position, and that the first position is zero. Suppose that there are $$n$$ elements in the array. Then we want to apply the permutation $$\pi(i) = (i+x) \pmod n$$. Two elements $$i,j$$ are in the same cycle of $$\pi$$ if $$i \equiv j \pmod {(n,x)}$$, which means the the cycle leaders (minimum elements of each cycle are $$0,\ldots,(n,x)-1$$. In other words, for each $$j < (n,x)$$, we need to consider the elements $$A[j],A[j+x],A[j+2x],\ldots,A[j+(n/(n,x)-1)x]$$ and rotate them one step to the right. This can be done using constant memory, and takes time $$O(n/(n,x))$$. Overall, the running time will be $$O(n)$$.

You don't actually need to determine $$(n,x)$$. Instead, you can simply count how many elements were touched. For example, you can consider the following pseudocode:

touched = 0
current = 0
while touched < n:
origin = current
element = A[current]
repeat:
current = (current + x) mod n
swap A[current] and element
touched = touched + 1
until current = origin
current = current + 1
end while


$$\texttt{index1}$$ is index of the first element of subarray 1, $$\texttt{index2}$$ is index of the first element of subarray 2 and $$\texttt{array_end}$$ is index of the last element in the array.

From $$\texttt{index2}$$ to $$\texttt{index2_i}$$ is a buffer that contains the elements to be inserted after $$\texttt{index2_i}$$ reaches array_end. From $$\texttt{index2_i}$$ to array_end are elements currently being inserted.

I fixed it by just moving $$\texttt{index2}$$ to $$\texttt{index2_i}$$ whenever $$\texttt{index1}$$ catches up (subarray 2 is made smaller, so $$\texttt{index2_i}$$ is not set to something less than or equal to $$\texttt{index1}$$). I might mark someone else's solution as the answer, but I am just including this for completeness. I am using this as a step in an $$O(n \log n)$$ implementation of in-place mergesort, if anyone was wondering.

Pseudo:

SwapSubArrays(index1, index2, array_end):
index2_i = index2
while (index1 < array_end):
if (index2_i > array_end):
index2_i = index2
if (index1 >= index2)
break
end if
end if

if (index1 >= index2):
index2 = index2_i
end if

Swap(index2, index2_i)

index1 = index1 + 1
index2_i = index2_i + 1
end while
end method


Source:

void swap(long* p1, long* p2, long* array_end) {
long* p2_i = p2;
while (p1 < array_end) {
if (p2_i > array_end) {
p2_i = p2;
if (p1 >= p2) {
break;
}
}

if (p1 >= p2) {
p2 = p2_i;
}

// swap *p1 and *p2_i
long* temp = p1;
*p1 = *p2_i;
*p2_i = temp;

++p1;
++p2_i;
}
}


In C++ we call this algorithm rotate. It was made famous by Sean Parent's C++ Seasoning talk in 2013 (discussion of rotate begins at 8:53).

Here is cppreference.com's possible implementation adapted into C.

/**
* @brief      Moves two ranges of elements in an array.
*
*             The elements in the range [first, n_first) to directly before
*             position last. Elements in the range [n_first, last) will be
*             moved to position first.
*
*             The ranges [, F) and [P, ) are unchanged.
*
* @param      first    The beginning of the first range
* @param      n_first  The beginning of the second range
* @param      last     The element directly after the end of the second range
*
* @return     The new location of first
*/
long* rotate(long* first, long* n_first, long* last)
{
if (first   == n_first) { return last; }
if (n_first == last)    { return first; }

long* write     = first;

{

long tmp = *write;

Forgive me for not using p1, p2, and array_end but I hope the documentation is clear enough. This code comes with no warranty, please ensure I have correctly translated the std::iter_swap(write++, read++);.