Question

Требуется отсортировать массив по неубыванию, используя сортировку слиянием.

Чтобы убедиться, что действительно используется сортировка слиянием, после каждого осуществленного слияния (то есть, когда соответствующий подмассив уже отсортирован!), требуется вывести индексы граничных элементов и их значения.

Answer 1

Код, который необходимо добавить, выделен на прикрепленной картинке красным прямоугольником.

Замечание: везде в коде не указан тип у vector. Необходимо указать тип, например vector<int>. В прикрепленном коде все исправлено.

Весь листинг:

#include <iostream>

#include <vector>

using namespace std;

vector<int> merge(vector<int> &A, vector<int> &B) {

   int i = 0;

   int j = 0;

   vector<int> C(A.size() + B.size());

   for (int k = 0; k < C.size(); k++) {

       // Если в массиве А все элементы закончились

       if (i == A.size()) {

           C[k] = B[j];

           j++;

           // Если в массиве B все элементы закончились

       } else if (j == B.size()) {

           C[k] = A[i];

           i++;

       } else if (A[i] <= B[j]) {

           C[k] = A[i];

           i++;

       } else {

           C[k] = B[j];

           j++;

       }

   }

   return C;

}

vector<int> merge_sort(vector<int> &V, int l, int r) {

   // Проверяем, не равна ли длина 1

   // Частный случай, при котором рекурсия завершается

   if (r - l == 1) {

       vector<int> res(1);

       res[0] = V[l];

       return res;

   }

   

   // Находим середину массива

   int m = (l + r) / 2;

   

   // Сортируем левую и правую половины независимо

   vector<int> left = merge_sort(V, l, m);

   vector<int> right = merge_sort(V, m, r);

   

   cout << l + 1 << ' '

       << r << ' '

       << right.front() << ' '

       << left.back() << endl;

   // Сливаем отсортированные половины

   return merge(left, right);

}

int main(){

   

   int n;

   cin >> n;

   vector<int> v(n);

   for (int i = 0; i < n; i++) {

       cin >> v[i];

   }

   

   // Вызов сортировки

   vector<int> v_sorted = merge_sort(v, 0, v.size());

   // Вывод результата

   for (int i = 0; i < v.size(); i++) {

       cout << v_sorted[i] << ' ';

   }

   return 0;

}