归并排序c++代码实现比较次数与移动次数

归并排序的比较次数和移动次数与具体实现有关，以下是一种简单的C++实现，给出比较次数和移动次数的计算方法。

void merge_sort(int arr[], int l, int r, int& cmp_cnt, int& mov_cnt) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    merge_sort(arr, l, mid, cmp_cnt, mov_cnt);
    merge_sort(arr, mid + 1, r, cmp_cnt, mov_cnt);
    int i = l, j = mid + 1, k = 0;
    int* tmp = new int[r - l + 1];
    while (i <= mid && j <= r) {
        cmp_cnt++;
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= r) {
        tmp[k++] = arr[j++];
    }
    for (int i = 0; i < k; i++) {
        mov_cnt++;
        arr[l + i] = tmp[i];
    }
    delete[] tmp;
}

int main() {
    int arr[] = {5, 4, 3, 2, 1};
    int cmp_cnt = 0, mov_cnt = 0;
    int n = sizeof(arr) / sizeof(arr[0]);
    merge_sort(arr, 0, n - 1, cmp_cnt, mov_cnt);
    cout << "比较次数：" << cmp_cnt << endl;
    cout << "移动次数：" << mov_cnt << endl;
    return 0;
}

以上代码中，cmp_cnt为比较次数，mov_cnt为移动次数。在归并排序中，每次比较会增加一次cmp_cnt，每次移动会增加一次mov_cnt。在最坏情况下，即数组完全逆序，比较次数为nlogn，移动次数为2nlogn。在平均情况下，比较次数为nlogn，移动次数为nlogn。