#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);
    }
}