归并排序
B合进A,A后面有空位给B. 既然有空位就直接从后面反着来(先放大的),逻辑上有足够空位所以遍历时不会把A前面元素弄乱。
void merge(vector<int>& A, int m, vector<int>& B, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0)
{
if (i < 0 || B[j] >= A[i]) A[k--] = B[j--]; //反过来就不用再翻转了。直接把大得放后面。
else A[k --] = A[i--];
}
}