是创建在归并操作上的一种有效的排序算法，效率为O(nlog n)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
递归法（Top-down）
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针到达序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
其实具体为创建两个函数，一个将原数组递归分裂成两半，一个进行归并。
算法复杂度：
比较操作的次数介于(nlog n)/2和(nlog n)-n+1。 赋值操作的次数是(2nlog n)。归并算法的时间复杂度为：O(nlogn)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#include <iostream>
#include <algorithm>
using namespace std;
//归并到开始数组中
void merge(int *a, int *left, int leftCount, int *right, int rightCount)
{
int i = 0, j = 0, k = 0;
while(i<leftCount && j<rightCount)
{
//将归并排序后的放回原数组
if(left[i] < right[i])
{
a[k++] = left[i++];
}
else
{
a[k++] = right[j++];
}
}
while(i < leftCount)
{
a[k++] = left[i++];
}
while(j < rightCount)
{
a[k++] = right[j++];
}
}
//将原数组分裂
void mergeSort(int *a, int len)
{
int mid, i, *left, *right;
if(len < 2)
{
return;
}
mid = len/2;
left = new int[mid];
right = new int[len-mid];
for(i=0; i<mid; i++)
{
left[i] = a[i];
}
for(i=mid; i<len; i++)
{
right[i-mid] = a[i];
}
mergeSort(left, mid);
mergeSort(right, len-mid);
merge(a, left, mid, right, len-mid);
delete[]left;
delete[]right;
}
int main()
{
int a[10] = {0,3,4,2,1,6,5,9,8,7};
int len = sizeof (a)/sizeof (a[0]);
mergeSort(a, len);
for(int i=0; i<len; i++)
{
cout << a[i] << ' ';
}
cout << endl;
return 0;
}
运行结果：
