Merge sort

The overall train of thought

Recursively, an array is divided into two parts until it cannot be merged (essentially one element on the left and one element on the right). The result of the merge is merged with another array.

Easy wrong points

Variable definition: l start position, mid position, r end position

• In merge, because you copy an array that starts at 0 on the left, the start index of the array on the right should be equal to the number of elements on the left (because the array starts at 0). I can easily write it as r-mid just to figure out where the right array starts
• During the comparison, rightIndex >= r should be written to determine that there are no elements in the right array

The specific code is as follows:

// Merge the elements into two parts, then merge the elements and repeat the above process

#include <stdio.h>
#include <vector>

using namespace std;

class MergeSortExe2 {
public:
    void sort(vector<int>& arr) {
        sort(arr, 0, (int)arr.size(a)- 1);
    }
    
private:
    void sort(vector<int>& arr, int l, int r) {
        if (l>=r) {
            return;
        }
        
        int mid = l + (r - l)/2;
        sort(arr, l, mid);
        sort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }
    
    // merge process:
    // copy the elements between [l...r]
    [mid] : [mid+1...r] : [mid+1...r]
    void merge(vector<int>& arr, int l, int mid, int r) {
        vector<int> tempArray;
        for (int i=l; i<=r; i++) {
            tempArray.push_back(arr[i]);
        }
        
        /// Count the number of numbers in the left and right arrays
        int leftNum = mid-l+1;
        int leftIndex = 0;
        int rightNum = r-mid;
// int rightIndex = r-mid-1; / / /!!!!!! If there are only 2 elements in the right array and 100 elements in the left array, the comparison and copying process uses the left array...
        int rightIndex = leftNum;
        int k = l;
        // As long as there is data in both arrays, we need to copy it
        while (leftIndex < leftNum || rightIndex < rightNum) {
            /// The first step is to handle the case where the left array has no elements
            /// The second part handles the case where there are no elements left in the right array
            // the third part compares whether the elements in the first array are smaller than the elements in the second array
            // step 4 copy the elements of the second array into the original array
            if (leftIndex >= leftNum) {
                arr[k] = tempArray[rightIndex];
                rightIndex++;
                k++;
} else if(rightIndex >= rightNum) {//! The size of the array should be smaller than that of the array
            } else if(rightIndex >= tempArray.size()) {
                arr[k] = tempArray[leftIndex];
                leftIndex++;
                k++;
            } else if(tempArray[leftIndex] <= tempArray[rightIndex]) {
                arr[k] = tempArray[leftIndex];
                leftIndex++;
                k++;
            } else{ arr[k] = tempArray[rightIndex]; rightIndex++; k++; }}}};Copy the code