[MahovIV]

Мне нужно создать программу, в которой используется сортировка слиянием. Нужно пересчитать количество перестановок. Программа выглядит так.

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

#include <iostream> #include <conio.h>   using namespace std;   #define maxn 173000   int a[maxn];   int n; int pr = 0;   void merge(int l, int r) {     if (r == l)         return;     if (r - l == 1) {         if (a[r] < a[l])             swap(a[r], a[l]);         return;     }     int m = (r + l) / 2;     merge(l, m);     merge(m + 1, r);     int buf[maxn];     int xl = l;     int xr = m + 1;     int cur = 0;     while (r - l + 1 != cur) {         if (xl > m) {             buf[cur++] = a[xr++];             pr++;             }         else if (xr > r) {             buf[cur++] = a[xl++];             pr++;             }         else if (a[xl] > a[xr]) {             buf[cur++] = a[xr++];             pr++;             }         else {              buf[cur++] = a[xl++];              pr++;              }       }     for (int i = 0; i < cur; i++)         a[i + l] = buf[i]; }   int main() {        cin >> n;       for (int i = 0; i < n; i++)         cin >> a[i];       merge(0, n - 1);       for (int i = 0; i < n; i++)         cout << a[i] << " ";         cout << pr << "\n";       getch();     return 0; }

Код

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

while (r - l + 1 != cur) {  if (xl > m) {             buf[cur++] = a[xr++];             pr++;             }         else if (xr > r) {             buf[cur++] = a[xl++];             pr++;             }         else if (a[xl] > a[xr]) {             buf[cur++] = a[xr++];             pr++;             }         else {              buf[cur++] = a[xl++];              pr++;              } }

делает перестановку.
Я не понимаю, где нужно добавить счётчик pr++? При maxn = 500000 программа принудительно закрывается. Какой вариант сортировки лишён этого недостатка?