Two ways to realize merge sort algorithm.

merge_sort_demo.cpp

#include <iostream>
#include <vector>

/* Copyright sanjay 2020 */
// 本程序使用两种方式实现归并排序，一种是c方式，一种是stl库方式
// 两者差异不大，仅传参类型不一样

namespace c_style {
    void Merge(int a[], int left, int mid , int right) {
        // 需要求得每一半的长度，以便申请空间
        int left_length = mid - left + 1;
        int right_length = right - mid;
        int* p_left = new int[left_length]();
        int* p_right = new int[right_length]();
        for(int i = 0; i < left_length; ++i) {
            p_left[i] = a[i + left];
        }
        for(int j = 0; j < right_length; ++j) {
            p_right[j] = a[j + mid + 1];
        }
        int i = 0, j = 0, k = left;
        while(i < left_length && j < right_length) {
            if (p_left[i] < p_right[j]) {
                a[k++] = p_left[i++];
            }
            else {
                a[k++] = p_right[j++];
            }
        }
        while(i < left_length) {
            a[k++] = p_left[i++];
        }
        while (j < right_length) {
            a[k++] = p_right[j++];
        }
        // 不要忘了删掉内存
        delete [] p_left;
        delete [] p_right;
    }

    void MergeSort(int a[], int left, int right) {
        if (left < right) {    // 这个判断条件很重要，这是递归结束的条件
            int mid = (left + right) / 2;
            MergeSort(a, left, mid);
            MergeSort(a, mid + 1, right);
            Merge(a, left, mid, right);
        }
    }

    void TestMergeSort() {
        int array[] = {9, 3, 7, 5, 6, 4, 8, 2};
        for(auto ele : array){
            std::cout << ele << " ";
        }
        std::cout << std::endl;
        MergeSort(array, 0, sizeof(array) / sizeof(int) -1);
        for(auto ele : array){
            std::cout << ele << " ";
        }
        std::cout << std::endl;
    }
}

namespace cpp_style {
    // 直接传入迭代器即可
    void Merge(
            std::vector<int>::iterator begin,
            std::vector<int>::iterator mid,
            std::vector<int>::iterator end) {
        int left_length = (mid - begin) + 1;
        int right_length = end - mid;
        std::vector<int> left(begin, mid + 1);
        std::vector<int> right(mid + 1, end);
        std::vector<int>::iterator p_left = left.begin();
        std::vector<int>::iterator p_right = right.begin();
        while(p_left != left.end() && p_right != right.end()) {
            if (*p_left < *p_right) {
                *(begin++) = *(p_left++);
            }
            else {
                *(begin++) = *(p_right++);
            }
        }
        while(p_left != left.end()) {
            *(begin++) = *(p_left++);
        }
        while(p_right != right.end()) {
            *(begin++) = *(p_right++);
        }
    }

    void MergeSort(std::vector<int>::iterator left, std::vector<int>::iterator right) {
        if(left != right) {
            std::vector<int>::iterator mid = left + (right - left) / 2;
            MergeSort(left, mid);
            MergeSort(mid + 1, right);
            Merge(left, mid, right);
        }
    }

    void TestMergeSort() {
        std::vector<int> vec{9, 3, 7, 5, 6, 4, 8, 2};
        MergeSort(vec.begin(), vec.end() - 1);
        for(auto e : vec) {
            std::cout << e << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
//    c_style::TestMergeSort();
//    int a[5] = {1,2,3,4,5};
//    std::vector<int> b(a, a + 5);  // 这个是最后元素最后一位
//    for(auto e : b){
//        std::cout << e << " ";
//    }
    cpp_style::TestMergeSort();

    return 0;
}