Given two sorted arrays A and B, where the end of A has enough space for B, write a method to merge B into A and sort them.
After getting this question, the most direct idea is to compare the elements in A and B and insert them into the arrays in order until all the elements in A and B are traversed. But there is a disadvantage in doing this: if the insertion position of the element is at the front of array A, the original array must be moved backward. This adds overhead. But we can use another method to insert elements at the end of array A. This way we won't have elements move! The code is as follows:
Copy the code code as follows: /*
* lastA: the actual number of elements in a lastB: the actual number of elements in b mergeIndex is the actual space size of the new array
*/
public static void mergeOrder(int[] a, int[] b, int lastA, int lastB) {
int indexA = lastA - 1;
int indexB = lastB - 1;
int mergeIndex = lastA + lastB - 1;
while (indexA >= 0 && indexB >= 0) {
if (a[indexA] > b[indexB]) {
a[mergeIndex] = a[indexA];
mergeIndex --;
indexA --;
} else {
a[mergeIndex] = b[indexB];
mergeIndex --;
indexB --;
}
}
while (indexB >= 0) {
a[mergeIndex] = b[indexB];
mergeIndex --;
indexB --;
}
}