这个归并排序算法的实现有什么问题吗？

Question

我知道合并排序算法有很多实现。我根据CLRS的Introduction to Algorithms一书中提供的算法实现了如下代码。

void merge_sort(int arr[], int starting_index, int ending_index) {  

    if(starting_index < ending_index) {         

        int middle_index = (starting_index + ending_index)/2;
        merge_sort(arr, starting_index, middle_index);  
        merge_sort(arr, middle_index+1, ending_index);
        merge_the_parts(arr, starting_index, middle_index, ending_index);   
    }
}

void merge_the_parts(int arr[], int starting_index, int middle_index, int ending_index) {

    int length_of_first_array = middle_index - starting_index + 1;
    int length_of_second_array = ending_index - middle_index;

    const int sentinel = INT_MAX;

    int left_arr[length_of_first_array + 1]; 
    int right_arr[length_of_second_array + 1]; 

    for(int i=0; i<length_of_first_array; i++) {
        left_arr[i] = arr[starting_index + i];      
    }

    // building second auxilliary
    for(int i=0; i<length_of_second_array; i++) {
        right_arr[i] = arr[(middle_index+1) + i];
    }

    left_arr[length_of_first_array] = sentinel; // use the sentinel as a condition
    right_arr[length_of_second_array] = sentinel;

    int i=0;
    int j=0;

    // the main merging loop
    for(int k=starting_index; k<ending_index+1; k++) {

        if(left_arr[i] <= right_arr[j]) {
            arr[k] = left_arr[i];
            i++;
        }

        else {
            arr[k] = right_arr[j];
            j++;
        }
    }   
}

该代码可以很好地对数组进行排序和倒置计数。但它给出了这个问题的错误答案 - https://www.spoj.com/problems/DCEPC206/。我已使用以下代码解决问题。

# include <iostream>
# include <climits>
using namespace std;

long int merge(int *arr, int l, int mid, int r) {

    int n1 = mid - l + 1;
    int n2 = r - mid;

    int *arrL = new int[n1 + 1];
    int *arrR = new int[n2 + 1];

    for(int i=0; i<n1; i++) {
        arrL[i] = arr[l + i];
    }

    for(int j=0; j<n2; j++) {
        arrR[j] = arr[(mid + 1) + j];
    }

    arrL[n1] = INT_MAX;
    arrR[n2] = INT_MAX;

    int i = 0, j = 0;
    long int count = 0;

    for(int k=l; k<=r; k++) {

        if(arrL[i] < arrR[j]) {
            arr[k] = arrL[i];
            if(arrR[j] != INT_MAX) {
                count += (arrL[i] * (n2 - j));
            }
            i++;
        } else {
            arr[k] = arrR[j];
            j++;
        }
    }

    delete[] arrL;
    delete[] arrR;

    return count;
}

long int countSeries(int *arr, int l, int r) {

    long int count = 0;

    if(l < r) {

        int mid = (l + r) / 2;
        count += countSeries(arr, l, mid);
        count += countSeries(arr, mid + 1, r);
        count += merge(arr, l, mid, r);
        return count;
    }

    return count;
}

Answer 1

你得到了错误的答案，因为考虑到问题中给出的范围，你只使用了 long 来保存如此大的 count 值。

使用long long可以容纳大值而不溢出：

long long count = 0;, long long countSeries(int *arr, int l, int r) {, count += (long long)arrL[i] * (n2 - j);

Here's a running code

这个归并排序算法的实现有什么问题吗？

Is there any problem with this implementation of the Merge Sort algorithm?

c++

arrays

algorithm

mergesort