Мы имеем массив размером m + n, в котором m элементов присутствует в отсортированном порядке и второй массив размера n, снова в отсортированном порядке. Мы хотите, чтобы оба они были отсортированы и присутствовали в первом массиве. Нет третьего массива должен быть дан.
Пример:
1, 3, 55, 66, 77, _, _, _
5, 9, 20
Ответ будет следующим:
1, 3, 5, 9, 20, 55, 66, 77
Сделайте обычную сортировку слияния, но сначала сравните самые большие числа, сохранив (перевернувшись) в конец первого массива, идущего назад. Таким образом, элементы, которые вы объединяете, никогда не перезаписываются (это легко понять, если вы думаете об этом на мгновение).
Переместить содержимое первого массива в конец первого массива, чтобы пустые элементы теперь находились в начале. Затем объедините две последовательности, как обычно, в первый массив.
На месте в основном требуется использовать только "постоянный" объем памяти, который не изменяется с разными размерами входных массивов. Однако сам вопрос выделяет дополнительный объем памяти, который совпадает с размером одного из двух входных массивов, что является O (n) памятью в худшем случае. Это в основном делает идею "на месте" бессмысленной...
Вопрос может быть лучше сформулирован как "слияние без дополнительной памяти", что является более точным описанием его реального намерения...
// merge the elements in B[] to A[], starting from the last one
void merge(int A[], int m, int B[], int n) {
// m-1 and n-1 represent the current element index in A[] and B[] respectively
while (n > 0) { // there are still elements in B[] not merged
if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[]
A[m+n-1] = A[m-1]; // move current element of A[] to its right position
--m; // decrease current element index of A[]
}
else { // current element in A[] <= current element in B[]
A[m+n-1] = B[n-1]; // move current element in B[] to its right position
--n; // decrease current element index of B[]
}
}
}