原理
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
图示过程
一分解
image.png
二合并
image.png
代码实现
// 交换 或者赋值排序
//中间数组排序
/**
* 合并两个有序数列
* array[left]~array[mid]为第一组
* array[mid+1]~array[right]为第二组
* temp[]为存放两组比较结果的临时数组
*/
void merge(int arr[], int left, int mid, int right) {
int temp[right - left + 1];
int i = left;
int j = mid + 1;
int t = 0;
// 比较左右两部分的元素，哪个小，把那个元素填入temp中
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
// 上面的循环退出后，把剩余的元素依次填入到temp中
// 以下两个while只有一个会执行
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
t = 0;
while (left <= right) {
arr[left++] = temp[t++];
}
}
void merge_sort_gui(int arr[], int left, int right) {
if (left == right) {
return;
}
int mid = left + (right - left)/2;
merge_sort_gui(arr, left, mid); // 递归归并左边元素
merge_sort_gui(arr, mid + 1, right); // 递归归并右边元素
merge(arr, left, mid, right); //再将两个有序数列合并
}
void merge_sort(int arr[], int length) {
merge_sort_gui(arr, 0, length -1);
}
