归并排序(英语：Merge sort，或mergesort)，是创建在归并操作上的一种有效的排序算法，效率为
(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用，且各层分治递归可以同时进行。归并排序适用于数据量大，同时解决了快速排序的痛点，大量重复数据并且链式结构同样适用(链式结构需要自己修改上述代码)，但是归并排序同样也有问题就是需要开辟额外空间。
归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
递归法(Top-down)
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
迭代法(Bottom-up)
原理如下(假设序列共有
个元素)：
将序列每相邻两个数字进行归并操作，形成
个序列，排序后每个序列包含两/一个元素
若此时序列数不是1个则将上述序列再次归并，形成
个序列，每个序列包含四/三个元素
重复步骤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);
}
?```!--more-->
