I tried to implement merge sort using C , however, something went wrong. I have no idea what is wrong.

The following code is what I wrote based on CLRS. I think it is quite easy to understand the meaning.

#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums, int p, int q, int r);
void mergeSort(vector<int>& nums, int p, int r){
    if (p < r) {
        int q = (p   r) / 2;
        mergeSort(nums, p, q);
        mergeSort(nums, q   1, r);
        merge(nums, p, q, r);
    }
}
void merge(vector<int>& nums, int p, int q, int r) {
    int s1 = p, s2 = q   1;
    vector<int> l1, l2;
    for (int i = s1; i <= q; i  ) {
        l1.push_back(nums[i]);
    }
    for (int i = s2; i <= r; i  ) {
        l2.push_back(nums[i]);
    }
    int left = 0, right = 0;
    int idx = 0;
    while (left < l1.size() && right < l2.size()) {
        if (l1[left] < l2[right]) {
            nums[idx] = l1[left  ];
        }
        else {
            nums[idx] = l2[right  ];
        }
        idx  ;
    }
    while (left < l1.size()) {
        nums[idx  ] = l1[left  ];
    }
    while (right < l2.size()) {
        nums[idx  ] = l2[right  ];
    }
}

int main() {
    vector<int> vect;
    vect.push_back(1);
    vect.push_back(3);
    vect.push_back(12);
    vect.push_back(23);
    vect.push_back(4);
    vect.push_back(11);
    vect.push_back(44);
    vect.push_back(322);
    mergeSort(vect, 0, vect.size() - 1);
    for (int i = 0; i < vect.size(); i  ) {
        cout << vect[i] << endl;
    }



    return 0;
}

I want to use the program to sort some integers, however, it only shows many duplicate numbers. What's going on? I don't think there is a problem of the merge function.

CodePudding user response：

The code needs a one line fix:

    int idx = p;    // not idx = 0

Optimized top down using arrays from Wiki article (note bottom up is slightly faster):

void TopDownMerge(int A[], int bgn, int mid, int end, int B[])
{
int i, j, k;
    i = bgn, j = mid, k = bgn;
    while(1){
        if(A[i] <= A[j]){               // if left smaller
            B[k  ] = A[i  ];            //  copy left element
            if(i < mid)                 //  if not end of left run
                continue;               //    continue
            do                          //  else copy rest of right run
                B[k  ] = A[j  ];
            while(j < end);
            break;                      //   and break
        } else {                        // else right smaller
            B[k  ] = A[j  ];            //  copy right element
            if(j < end)                 //  if not end of right run
                continue;               //    continue
            do                          //  else copy rest of left run
                B[k  ] = A[i  ];
            while(i < mid);
            break;                      //   and break
        }
    }
}

void TopDownSplitMerge(int B[], int bgn, int end, int A[])
{
    if (end - bgn <= 1)                 // if run size == 1
        return;                         //   consider it sorted
    int mid = (end   bgn) / 2;
    TopDownSplitMerge(A, bgn, mid, B);
    TopDownSplitMerge(A, mid, end, B);
    TopDownMerge(B, bgn, mid, end, A);
}

void TopDownMergeSort(int A[], int n)   // n = size (not size-1)
{
    if(n < 2)
        return;
    int *B = new int [n];               // 1 time allocate and copy
    for(size_t i = 0; i < n; i  )
        B[i] = A[i];
    TopDownSplitMerge(B, 0, n, A);      // sort data from B[] into A[]
    delete B;
}

CodePudding user response：

Afterwards, I finally get to fix the bugs of my program. After modification, here is the code:

class Solution {
public:
    vector<int> temp;
    vector<int> sortArray(vector<int>& nums) {
        temp.resize((int)nums.size(), 0);
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void mergeSort(vector<int>& nums, int start, int end) {
        if (start >= end)   return;
        int middle = (start   end) / 2;
        mergeSort(nums, start, middle);
        mergeSort(nums, middle   1, end);
        merge(nums, start, middle, end);
    }
    void merge(vector<int>& nums, int leftStart, int middle, int rightEnd) {
        int leftEnd = middle;
        int rightStart = middle   1;
        int i = leftStart, j = rightStart;
        int index = 0;
        while (i <= leftEnd && j <= rightEnd) {
            if (nums[i] < nums[j]) {
                temp[index] = nums[i  ];
            }
            else {
                temp[index] = nums[j  ];
            }
            index  ;
        }
        while (i <= leftEnd) {
            temp[index  ] = nums[i  ];
        }
        while (j <= rightEnd) {
            temp[index  ] = nums[j  ];
        }
        for (int i = 0; i < rightEnd - leftStart   1; i  ) {
            nums[i   leftStart] = temp[i];
        }
    }
};

Here is something should be careful next time:

1. In the merge part, it is difficult to merge in place. It'd be better to use another temp array to store the merged results and update to the target array (nums in this case).
2. Readable identifers is very recommended (Although the pseudocode of CLRS may not use that part).
3. Need to use debuggers to find the bug of program {However, it takes like forever to load local variables of VS Code debugers.