归并排序

将⼀个⼤的⽆序数组有序，我们可以把⼤的数组分成两个，然后对这两个数组分别进⾏排序，之后在把这两个数组合并成⼀个有序的数组。由于两个⼩的数组都是有序的，所以在合并的时候是很快的。 通过递归的⽅式将⼤的数组⼀直分割，直到数组的⼤⼩为 1，此时只有⼀个元素，那么该数组就是有序的了，之后 再把两个数组⼤⼩为1的合并成⼀个⼤⼩为2的，再把两个⼤⼩为2的合并成4的 … 直到全部⼩的数组合并起来。

该算法是采⽤分治法（Divide and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为2-路归并。

算法思想 1、把⻓度为n的输⼊序列分成两个⻓度为n/2的⼦序列； 2、对这两个⼦序列分别采⽤归并排序； 3、 将两个排序好的⼦序列合并成⼀个最终的排序序列。[leetcode 21. 合并两个有序链表](# leetcode 21. 合并两个有序链表)

性能分析

分组的深度为O(logN) 合并的复杂度为O(N) 时间复杂度O(NlogN) 优点:时间复杂度低

//mergeSort.h
#include <vector>
#include <cstring>                                                                            
using std::vector;

void my_merge(vector<int>& nums, int left, int mid, int right);
void merge_sort(vector<int>& nums, int left, int right);

//mergeSort.cc
#include "mergeSort.h"

void my_merge(vector<int>& nums, int left, int mid, int right) {//类比合并2个链表
    vector<int> buffer(nums);
    int i = left;   //i表示左半边的下标，j表示右半边的下标，k表示结果的下标
    int j = mid + 1;
    int k = left;
    while(i <= mid && j <= right) {
        if(buffer[i] < buffer[j]) {
            nums[k] = buffer[i];
            ++i;
        }   
        else {
            nums[k] = buffer[j];
            ++j;
        }   
        ++k;
    }   
    //剩余的数据
    while(i <= mid){    //i的结束时是等于mid ，而不是nums.size()                 
        nums[k] = buffer[i];
        ++k;
        ++i;
    }   
    while(j <= right) {
        nums[k] = buffer[j];
        ++k;
        ++j;
    }   
}

void merge_sort(vector<int>& nums, int left, int right) {
    if(left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);
        my_merge(nums, left, mid, right);
    }   
}

• 每次都创建buffer太浪费

改进

class Solution {
public:
    void mergesort(vector<int>& nums, int left, int right, vector<int>& buffer) {
        if(left >= right) {
            return;
        }
        int middle = left + (right - left) / 2;
        mergesort(nums, left, middle, buffer);
        mergesort(nums, middle + 1, right, buffer);
        int v1 = left;
        int v2 = middle + 1;
        int index = left;
        while(v1 <= middle && v2 <= right) {
            if(nums[v1] <= nums[v2]) {
                buffer[index++] = nums[v1++];
            }
            else {
                buffer[index++] = nums[v2++];
            }
        }
        while(v1 <= middle) {
            buffer[index++] = nums[v1++];
        }
        while(v2 <= right) {
            buffer[index++] = nums[v2++];
        } 

        std::copy(buffer.begin() + left, buffer.begin() + right + 1, nums.begin() + left);
    }
    vector<int> sortArray(vector<int>& nums) {
        vector<int> buffer(nums.size());
        mergesort(nums, 0, nums.size() - 1, buffer);
        return nums;
    }
};