c++14 - Merge Sort implementation outputs wrong results

Question

I am trying to implement Merge Sort in C++ 14. I've written the full code and proof-read it multiple times for logical faults but can't find any. But the code outputs a wrong sorted array that sometimes even contains duplicate elements and/or elements that were never input to the array in the first place.

Here's my code:

#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
void merge_sort(vector<int>&, int, int);
void print_vector(vector<int>&);
void merge(vector<int>&, int, int, int);

int main() {
    int arr_len = 0;
    cout << "Enter the length of the array to be sorted: " << endl;
    cin >> arr_len;

    vector<int> arr(arr_len);

    cout << "Enter the elements of the array: " << endl;
    for (int i = 0; i < arr_len; i++) {
        int buff;
        cin >> buff;
        arr[i] = buff;
    }

    cout << "The elements entered in the unsorted vector are: " << endl;
    print_vector(arr);

    merge_sort(arr, 0, arr_len - 1);

    cout << "After Merge sorting, the elements in the vector are: " << endl;
    print_vector(arr);

    return 0;
}

void print_vector(vector<int>& arr) {
    for (auto itr = arr.begin(); itr != arr.end(); ++itr) {
        cout << *itr << " ";
    }
    cout << endl;
}

void merge_sort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;           // used this instead of (low + high) / 2 to avoid overflow problems
        merge_sort(arr, low, mid);                  // recursive call to merge_sort with high = mid's updated value
        merge_sort(arr, mid + 1, high);
        merge(arr, low, mid, high);                 // call to merge to sort and merge the fragmented arrays.
    }
}

void merge(vector<int>& arr, int low, int mid, int high) {
    int l_arr_len = mid - low + 1;
    int r_arr_len = high - mid;
    vector<int> l_arr(l_arr_len);
    vector<int> r_arr(r_arr_len);

    for (int i = 0; i < l_arr_len; i++) {        // initialise elements of temp_arr1 (l_arr) to 0.
        l_arr[i] = 0;
    }

    for (int i = 0; i < r_arr_len; i++) {        // initialise elements of temp_arr2 (r_arr) to 0.   
        r_arr[i] = 0;
    }

    for (int i = 0; i < l_arr_len; i++) {        // transfer elements from arr to l_arr, upto length of the fragmented l_arr.
        l_arr[i] = arr[low + i];
    }

    for (int i = 0; i < r_arr_len; i++) {        // transfer remaining elements from arr to r_arr, upto length of the fragmented r_arr.
        r_arr[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = 0;
    while (i < l_arr_len && j < r_arr_len) {            // compare and replace elements in the mother array arr
        if (l_arr[i] <= r_arr[j]) {                      // smallest element goes first
            arr[k++] = l_arr[i++];
        } else {
            arr[k++] = r_arr[j++];
        }
    }

    while (i < l_arr_len) {                  // write remaining elements in the left_arr fragment to mother array arr
        arr[k++] = l_arr[i++];
    }

    while (j < r_arr_len) {                  // write remaining elements in the left_arr fragment to mother array arr
        arr[k++] = r_arr[j++];
    }
}

For an input array of elements [2, 9, 4, 5, 7], the correct sorted result would have been: [2, 4, 5, 7, 9].

But my implementation outputs: [5, 5, 7, 7, 9]. I don't understand where the duplicate elements came from and why they replaced the original elements. While I've tried to add comments to almost statement out there for ease of access of the SO community, some of those may be redundant.

Since I'm out of my wits, please help me correct my code. You can point out what's wrong & where if that's what's convenient.

Thanks in advance! :)

标签： c++14mergesort

Answer 1

主要问题是别人发现的，k必须初始化为，low而不是0.

您应该查看更多问题：

• 数组索引值和大小的正确类型是size_t, not int，它的范围可能要小得多。

• 传递最后一个元素的索引而不是排除的上限会产生带有索引调整的繁琐代码。

• 无需初始化临时向量，您应该只复制内容，或者更好地从数组切片构造它们。

• print_vector应该const参考一下。

这是修改后的版本：

#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
void merge_sort(vector<int>&, size_t, size_t);
void merge(vector<int>&, size_t, size_t, size_t);
void print_vector(const vector<int>&);

int main() {
    size_t arr_len = 0;
    cout << "Enter the length of the array to be sorted: " << endl;
    cin >> arr_len;

    vector<int> arr(arr_len);

    cout << "Enter the elements of the array: " << endl;
    for (size_t i = 0; i < arr_len; i++) {
        cin >> arr[i];
    }

    cout << "The elements entered in the unsorted vector are: " << endl;
    print_vector(arr);

    merge_sort(arr, 0, arr_len);

    cout << "After Merge sorting, the elements in the vector are: " << endl;
    print_vector(arr);

    return 0;
}

void print_vector(const vector<int>& arr) {
    for (auto itr = arr.begin(); itr != arr.end(); ++itr) {
        cout << *itr << " ";
    }
    cout << endl;
}

void merge_sort(vector<int>& arr, size_t low, size_t high) {
    if (high - low > 1) {
        size_t mid = low + (high - low) / 2;    // used this instead of (low + high) / 2 to avoid overflow problems
        merge_sort(arr, low, mid);              // recursive call to merge_sort with high = mid's updated value
        merge_sort(arr, mid, high);
        merge(arr, low, mid, high);             // call to merge to sort and merge the fragmented arrays.
    }
}

void merge(vector<int>& arr, size_t low, size_t mid, size_t high) {
    size_t l_arr_len = mid - low;
    size_t r_arr_len = high - mid;
    vector<int> l_arr(l_arr_len);
    vector<int> r_arr(r_arr_len);

    for (size_t i = 0; i < l_arr_len; i++) {    // transfer elements from arr to l_arr, upto length of the fragmented l_arr.
        l_arr[i] = arr[low + i];
    }
    for (size_t i = 0; i < r_arr_len; i++) {    // transfer remaining elements from arr to r_arr, upto length of the fragmented r_arr.
        r_arr[i] = arr[mid + i];
    }

    size_t i = 0, j = 0, k = low;
    while (i < l_arr_len && j < r_arr_len) {    // compare and replace elements in the mother array arr
        if (l_arr[i] <= r_arr[j]) {             // smallest element goes first
            arr[k++] = l_arr[i++];
        } else {
            arr[k++] = r_arr[j++];
        }
    }
    while (i < l_arr_len) {                  // write remaining elements in the left_arr fragment to mother array arr
        arr[k++] = l_arr[i++];
    }
    while (j < r_arr_len) {                  // write remaining elements in the left_arr fragment to mother array arr
        arr[k++] = r_arr[j++];
    }
}