归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的，为（）。1945年由首次提出。该算法是采用（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序适用于数据量大，同时解决了快速排序的痛点，大量重复数据并且链式结构同样适用（链式结构需要自己修改上述代码），但是归并排序同样也有问题就是需要开辟额外空间。

归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

递归法（Top-down）

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

迭代法（Bottom-up）

原理如下（假设序列共有个元素）：

1. 将序列每相邻两个数字进行，形成个序列，排序后每个序列包含两/一个元素

2. 若此时序列数不是1个则将上述序列再次归并，形成个序列，每个序列包含四/三个元素

3. 重复步骤2，直到所有元素排序完毕，即序列数为1

// 归并排序 递归法,// 注意返回的才是排好序的数组，原数组没有变动function _merge(left, right){    // 创建大小为left + right 大小的数组    let result = [];    while(left.length > 0 && right.length > 0){        if (left[0] < right[0]){            result.push(left.shift());        } else{            result.push(right.shift());        }    }    return result.concat(left, right);}function mergeSort(arr){    if (arr.length <= 1) return arr;    let mid = arr.length >> 1;    let left = arr.slice(0, mid);    let right = arr.slice(mid);    return _merge(mergeSort(left), mergeSort(right));}

c语言实现

​```c// 归并排序， 递归法void sortMergeRecursive(int *arr, int * reg, int start, int end){    if (start >= end) return;    int len = end - start;    int mid = (len >> 1) + start;    int startLfet = start, endLeft = mid;    int startRight = mid + 1, endRight = end;    sortMergeRecursive(arr, reg, startLfet, endLeft);    sortMergeRecursive(arr, reg, startRight, endRight);        int k = start;        // 左右两个数组按照大小合并成一个    while (startLfet <= endLeft && startRight <= endRight){        reg[k++] = arr[startLfet] < arr[startRight] ? arr[startLfet++] : arr[startRight++];    }    // 把另一个数组剩余的元素全部拷贝到reg数组里    while (startLfet <= endLeft){        reg[k++] = arr[startLfet++];    }    while (startRight <= endRight){        reg[k++] = arr[startRight++];    }    // 更新arr    for (k = start; k <= end; k++){        arr[k] = reg[k];    }}// 归并排序 入口void sortMerge(int *arr, const int len){    int reg[len];    sortMergeRecursive(arr, reg, 0, len-1);}​```