#include<iostream>

#include<vector>

using namespace std;

void sort_merge_recursive(vector<int>& data, int left, int right);

void merge(vector<int>& data, int left, int mid, int right);

int main()

{

    // 首先找出待排序列中最小的数,然后用这个数和原序列中的第一个数交换位置;

    // 其次,找出第二小的和原第二个数交换位置;

    // 依次顺序直到找到第二大的数,之后原数列完全变成有序数列.

    vector<int> data = { 3,0,5,2,7,8,9,6,1 };

    //获取序列元素个数

    int length = 9;

    int left = 0;

    int right = 8;

    sort_merge_recursive(data, left, right);

    for (int i = 0; i < length; i++)

    {

        cout << data[i] << "   ";

    }

}

void sort_merge_recursive(vector<int> &data, int left, int right)

{

    if (left < right)//暗含如果left>=right就不做任何操作，因为这个时候表示已经分解到只剩一个元素了，天然有序

    {

        //将序列一分为二获取中间位置

        int mid = (left + right) / 2;

        //递归处理两个子序列使之有序

        sort_merge_recursive(data, left, mid);

        sort_merge_recursive(data, mid + 1, right);

        //合并两个有序子序列

        merge(data, left, mid, right);

    }

}

void merge(vector<int> &data, int left, int mid, int right)

{

    //将有序的两个子序列合并起来

    //获取两个子序列的第一个元素

    int i = left;

    int j = mid + 1;

    //创建临时容器来保存合并结果，同时指定容器大小

    vector<int> temp;

    temp.resize(right - left + 1);//从图中最底下开始往上合并，每一次因为要合并两个子序列，所以容器大小要从新设置

    //开始合并

    int k = 0;//临时容器的索引

    while (i <= mid && j <= right)

    {

        if (data.at(i) <= data.at(j))//如果左边的值元素值小于右边的

        {

            temp.at(k++) = data.at(i++);//先把小的放到数组前面

        }

        else

        {

            temp.at(k++) = data.at(j++);

        }

    }

    //到这里肯定已经有一个子序列的所有元素已经完全放到了容器里，接着放另一个剩下的元素

    while (i <= mid)//因为不知道是哪个完全放进去了，用这种方式来判断

    {

        temp.at(k++) = data.at(i++);

    }

    while (j <= right)

    {

        temp.at(k++) = data.at(j++);

    }

    //只能通过这样的方式将临时容器元素复制给原始容器得到结果

    for (int n = 0; n < k; n++)

    {

        data.at(left++) = temp.at(n);

    }

}