归并排序

归并字面上的意思是合并，归并算法的核心思想是分治法，就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。

我们以[ 8，2，5，9，7 ]这组数字来举例

首先，一刀切两半：

再切：

再切：

粒度切到最小的时候，就开始归并

数据量设定的比较少，是为了方便图解，数据量为单数，是为了让你看到细节，下面我画了一张更直观的图可能你会更喜欢：

代码实现

void sort(vector<int> &arr)
{
    vector<int> tmp(arr.size());
    sort(arr, tmp, 0, arr.size()-1);
}

void sort(vector<int> &arr, vector<int> &tmp, int start, int end)
{
    if(end <= start) return;

}

void sort(vector<int> &arr, vector<int> &tmp, int start, int end)
{
    if(end <= start) return;

    int mid = start + (end - start) / 2;

    sort(arr, tmp, start, mid);
    sort(arr, tmp, mid+1, end);

    merge(arr, tmp, start, mid, end);
}

void merge(vector<int>& arr, vector<int>& tmp, int start, int mid, int end)
{
    for(int i = start; i <= end; i++) {
        tmp[s] = arr[s];
    }

    int left = start;
    int right = mid +1;
    for(int j = start; j <= end; j++) {
        if(left > mid) {
            //如果左边的首位下标大于中部下标，证明左边的数据已经排完了。
            arr[j] = tmp[right++];
        } else if(right > end) {
            //如果右边的首位下标大于了数组长度，证明右边的数据已经排完了。
            arr[j] = tmp[left++];
        } else if(tmp[right] < tmp[left]) {
            //将右边的首位排入，然后右边的下标指针+1。
            arr[j] = tmp[right++];
        } else {
            //将左边的首位排入，然后左边的下标指针+1。
            arr[j] = tmp[left++];
        }
    }
}

我们可以发现 merge 方法中只有一个 for 循环，直接就可以得出每次合并的时间复杂度为 \(O(n)\) ，而分解数组每次对半切割，属于对数时间 \(O(\log n)\) ，合起来等于 \(O(\log_2{n})\) ，也就是说，总的时间复杂度为 \(O(n\log n)\) 。