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

Question

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

Answer 1

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

Answer 2

$\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;
  }
}

Answer 3

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* read      = n_first;
   long* write     = first;
   long* next_read = first; // read position for when "read" hits "last"

   while(read != last)
   {
      if (write == next_read) { next_read = read; } // track where "first" went

      long tmp = *write;
      *write = *read
      *read = tmp;

      read++
      write++;
   }

   // rotate the remaining sequence into place
   rotate(write, next_read, last);
   return 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++);.