容易理解的归并排序（C语言）

以二路归并为例，可简单理解为：
把一个大的数组拆分成两个数组，拆出来的两个数组再分别拆出两个数组，以此类推，直到每个数组只有一个元素。然后将这些只有一个元素的数组两两合并到一个临时数组，即可完成排序。

#include 
using namespace std;

void merge(int arr[], int left, int mid, int right) {
	int i, j, k;
	int n1 = mid - left + 1; //n1为左数组的下标
	int n2 = right - mid; //n2为右数组的上标
	int L[n1], R[n2]; //分别表示左右数组的临时存储数组

	//给左右临时数组赋值
	for (i = 0; i < n1; i++) {
		L[i] = arr[left + i];
	}
	for (j = 0; j < n2; j++) {
		R[j] = arr[mid + 1 + j];
	}

	i = 0, j = 0, k = left;
	while (i < n1 && j < n2) {//将左右数组合并到arr[1..right]
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		} else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}

	//左或右数组其中某个并完了，将另一个数组直接接在arr上即可
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

void mergeSort(int arr[], int left, int right) {
	if (left < right) {
		int mid = left + (right - left) / 2;
		mergeSort(arr, left, mid);//不断的切分左右数组，
		mergeSort(arr, mid + 1, right);//直到每个数组只有1个元素，
		merge(arr, left, mid, right);//即可开始排序
	}
}

int main() {
	int arr[7] = {7, 6, 5, 4, 3, 2, 1};
	mergeSort(arr, 0, 6);
	for (int i = 0; i < 7; i++) {
		cout << arr[i] << " ";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

运行截图：