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