归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
归并排序算法依赖归并操作。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序在众多排序算法中既是稳定排序，效率也比较高，同时，归并排序不仅可以用于内排序，还可以用于外排序。
1.两个有序数列的合并
设两个有序数列放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量 R1中，待合并完成后将 R1 复制回 R[low..high]中。
（1）合并过程
合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。
合并时依次比较 R[i]和 R[j]的关键字，取关键字较小的记录复制到 R1[p]中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p 加 1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕，此时将另一非空的子文件中剩余记录依次复制到 R1 中即可。
（2）动态申请 R1
实现时，R1 是动态申请的，因为申请的空间可能很大，所以在工程上应用时，可能需要加入申请空间是否成功的处理。
2.归并排序的实现
（1）二路归并的思路
将数组划均分为两个子数组；
对两个字数组进行排序；
将排序好的两个字数组归并。
所谓 N路归并 是指将数组均分为N个子数组，将字数组排序后再归并。二路归并是归并排序的最一般的情况。
（2）归并排序实现的一般化过程
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
（3）实现过程
|
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
86
87
88
89
90
91
92
93
94
95
96
97
|
public
class
MergeSort {
public
static
void
main(String[] args){
int
[] arr=
new
int
[]{
8
,
7
,
6
,
5
,
4
,
3
,
2
,
1
};
for
(
int
i=
0
;i<arr.length;i++){
System.out.print(arr[i]+
","
);
}
//想起引用传递和值传递的问题，数组是引用传递，不需要什么返回值
sort(arr,arr.length);
System.out.println(
"排序后"
);
for
(
int
i=
0
;i<arr.length;i++){
System.out.print(arr[i]+
","
);
}
}
public
static
void
sort(
int
[] arr,
int
n){
if
(arr==
null
|| n<
2
){
return
;
//边界情况
}
divide(arr,
0
,n-
1
);
}
/**
*
* @param arr 待排序数组
* @param left 待排序区间左侧下标
* @param right 待排序区间右侧下标
*/
public
static
void
divide(
int
[] arr,
int
left,
int
right){
if
(left>=right){
return
;
}
int
m=(left+right)/
2
;
//从中间开始分成两个区间进行归并
divide(arr,left,m);
//一直递归划分直到区间长度为1
divide(arr,m+
1
,right);
//开始逐级往上进行归并操作
binaryMerge(arr,left,m,right);
//第一次进行merge操作的递归栈最深层此时是merge(arr,0,0,1)
}
/**
* 对数组arr[left...right]位置进行递归的归并排序
* @param arr
* @param left
* @param rigtht
* @param temp
*/
public
static
void
binaryMerge(
int
[] arr,
int
left,
int
m,
int
right){
/**
* 归并排序的时间复杂度为O(n),指的就是最大长度为n的临时数组
*/
int
[] temp=
new
int
[right-left+
1
];
int
l=left;
//
int
r=m+
1
;
//
int
index=
0
;
//
while
(l<=m && r<=right){
if
(arr[l]<arr[r]){
temp[index]=arr[l];
index++;
l++;
}
else
{
temp[index]=arr[r];
index++;
r++;
}
}
/**
* 交换完了如果哪一侧数组还有剩余，则全部赋值
* 实际的一次归并下面的两个while循环只会执行一个
* warn!不要漏了等于的情况！否则会每两个元素丢失一个元素
*/
while
(l<=m){
temp[index]=arr[l];
index++;
l++;
}
while
(r<=right){
temp[index]=arr[r];
index++;
r++;
}
/**
* 用临时数组的部分排序的序列全部替换待排序数组中对应的部分
* 这里应该用temp.length，不能用arr.length
*/
for
(
int
i=
0
;i<temp.length;i++){
//注意是left，此时的l是已经变化了的
arr[left+i]=temp[i];
}
}
}
|
（4）时间和空间复杂度
归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，
比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。
3.空间复杂度为O(1)的归并排序
归并排序的空间复杂度为O(N)，
通过优化可以把空间复杂度降为O(1)，通过手摇算法，
但实际上通过手摇算法后，此时的时间复杂度会上升。
4.多路归并排序
归并排序的思想可以用于外排序。
外排序是相对内排序而言的，在常规的小规模排序过程中，都是直接在内存中对数据进行排序处理的，而对于数据量极大的排序问题，这种方式是不现实的。
这个时候就要通过外排序来进行，先将数据划分成多个规模能在内存中处理的子集，对各个子集排序后存放在临时的磁盘文件上，然后再将这些子集归并到输出文件中。
这个过程要使用到多路归并。
本文转自邴越博客园博客，原文链接：http://www.cnblogs.com/binyue/p/3421123.html，如需转载请自行联系原作者
