[MahovIV]

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

Код:

#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;
}

Код

Код:

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 программа принудительно закрывается. Какой вариант сортировки лишён этого недостатка?