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 &lt; array_end) {
    if (p2_i &gt; array_end) {
      p2_i = p2;
    }

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

    ++p1;
    ++p2_i;
  }
}
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 &lt; (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 &lt; 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