归并过程分解
假设两个有序表分别为a,b，最后归并到r表中。
归并过程：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
示例分解
假设原始序列为：{6，202，100，301，38，8，1}，其长度len = 7，归并过程：
1、第一次归并：先中分得到mid索引为3，递归归并左半部分{6， 202， 100， 301}，对这个子序列又中分为{6, 202}和{100, 301}，此时这两个子序列已有序；递归归并右半部分{38, 8, 1}，对这个子序列又中分为{38, 8}和{1}，归并后形成{8，38}和{1}，共比较3次
2、第二次归并：第一次归并后变成{6,202},{100,301},{8,38},{1}，即{6， 202，100，301，8，38，1}，再中分得到{6，202，100，301}和{8，38，1}，分别递归归并后为{6，100，202，301}新序列和{1，8，31}新序列，共比较3+1=4次。
3、第三次归并：第二次归并后，得到的两个有序的子序列为{6，100，202，301}和{1，8，38}，这一次是递归回到第一层了，已经是中分了，直接比较和复制到新的r即可。最终得到{1，6，8，38，100，202，301}，共比较4次（6与1比较，6与8比较，100与8比较，100与38比较）。
这个序列从无序到有序总共比较了3+4+4=11次。
算法复杂度分析
归并排序的效率是比较高的，假设数列长度为N，采用中分法的方式将数列分开成若干个小数列一共要log2N 步，每步都是一个合并有序数列的过程，时间复杂度可以记为O ( N )，故一共为O ( N * log2N)。
因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在常用的几种排序方法（快速排序，归并排序，希尔排序，堆排序）中也是效率比较高的。
时间复杂度：O ( N * log2N )
C语言实现
|
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
/**
* 归并排序算法
*
* @param list 待排序的序列
* @param first 子序列的起点索引
* @param last 子序列的终点索引
* @param temp 临时数组，用于将两个子序列二路归并时存储
*/
void mergeSort(int list[], int first, int last, int temp[]) {
if (first < last) {
int mid = (first + last) / 2;
// 递归归并中分左子序列，使子序列有序
mergeSort(list, first, mid, temp);
// 递归归并中分右子序列，使子序列有序
mergeSort(list, mid + 1, last, temp);
// 最后二路归并，使序列成有序
// 必须明白的一点，每次中分递归归并都需要二路归并，因为中分后的任意子序列
// 在有序后，都要二路归并成一个序列
mergeList(list, first, mid, last, temp);
}
}
/**
* 二路归并list[first...mid]子序列与list[mid+1...last]
*
* @param list 序列
* @param first 左子序列的起点
* @param mid 序列中间分割点
* @param last 右序列终点
* @param temp 临时序列，用于将两个无序的子序列归并到temp中，使之有序
*/
void mergeList(int list[], int first, int mid, int last, int temp[]) {
int leftIndex = first;
int leftEndIndex = mid;
int rightIndex = mid + 1;
int rightEndIndex = last;
int tempIndex = 0;
// 寻找两个子序列，顺序遍历，将值小的复制到临时数组中，直到其中一个子序列遍历完毕
while (leftIndex <= leftEndIndex && rightIndex <= rightEndIndex) {
// 值小的就复制到临时数组中
if (list[leftIndex] <= list[rightIndex]) {
temp[tempIndex] = list[leftIndex];
tempIndex++;
leftIndex++;
} else {
temp[tempIndex] = list[rightIndex];
tempIndex++;
rightIndex++;
}
}
// 有可能左子序列更长，因此将剩下的部分直接复制到临时数组中
while (leftIndex <= leftEndIndex) {
temp[tempIndex++] = list[leftIndex++];
}
// 有可能右子序列更长，因此将剩下的部分直接复制到临时数组中
while (rightIndex <= rightEndIndex) {
temp[tempIndex++] = list[rightIndex++];
}
// 最后还需要将有序的临时数组复制到原始序列中
for (int i = 0; i < tempIndex; ++i) {
list[first + i] = temp[i];
}
// 这里添加一个打印，记录归并
NSMutableString *str = [[NSMutableString alloc] init];
for (int i = 0; i < sizeof(list) - 1; ++i) {
if (i == 0) {
[str appendFormat:@"%d", list[i]];
} else {
[str appendFormat:@", %d", list[i]];
}
}
NSLog(@"此次二路归并后，得到的序列为：(%@)", str);
}
|
测试：
|
1
2
3
4
5
|
int list[] = {6, 202, 100, 301, 38, 8, 1};
int temp[7] = {0};
mergeSort(list, 0, 7-1, temp);
|
打印效果：
|
1
2
3
4
5
6
7
8
|
此次二路归并后，得到的序列为：(6, 202, 100, 301, 38, 8, 1)
此次二路归并后，得到的序列为：(6, 202, 100, 301, 38, 8, 1)
此次二路归并后，得到的序列为：(6, 100, 202, 301, 38, 8, 1)
此次二路归并后，得到的序列为：(6, 100, 202, 301, 8, 38, 1)
此次二路归并后，得到的序列为：(6, 100, 202, 301, 1, 8, 38)
此次二路归并后，得到的序列为：(1, 6, 8, 38, 100, 202, 301)
|
从打印结果可以看出来，果然与我们前面的算法分析是一样的。