Это всего лишь фаза слияния сортировки слиянием,
- скопировать все элементы a2
(1,2,3,4) в конце a1 (5,6,7,8), теперь a1 будет содержать (4,5,6,7,8,1,2,3,4)
- Теперь вызовите алгоритм слияния ниже
inPlaceMerge(collection, 0<low>,3<mid>,7<high>);
вот алгоритм на Java,
public static <T extends Comparable<? super T>> void inPlaceMerge(T[] collection, int low, int mid, int high) {
int left = low;
int right = mid + 1;
if(collection[mid].equals(collection[right])) {
return ;//Skip the merge if required
}
while (left <= mid && right <= high) {
// Select from left: no change, just advance left
if (collection[left].compareTo(collection[right]) <= 0) {
left ++;
} else { // Select from right: rotate [left..right] and correct
T tmp = collection[right]; // Will move to [left]
rotateRight(collection, left, right - left);
collection[left] = tmp;
// EVERYTHING has moved up by one
left ++; right ++; mid ++;
}
}
}
private static <T extends Comparable<? super T>> void rotateRight(T[] collection, int left, int numberOfElements) {
System.arraycopy(collection, left, collection, left+1, numberOfElements);
}
Вот модульный тест
@Test
public void inPlaceMergeFirstTest() {
Integer[] collection = new Integer[]{5,6,7,8,1,2,3,4};
ArrayUtils.<Integer>inPlaceMerge(collection, 0,3,7);
Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
assertThat(collection, equalTo(result));
}